Auto merge of #64736 - Nashenas88:mir_predecessors_cache_cleanup, r=oli-obk

Remove interior mutability in mir predecessors cache

74 files changed, 942 insertions, 590 deletions

diff --git a/src/librustc/arena.rs b/src/librustc/arena.rs
index 1d6a3420ed9..364a35f1b6f 100644
--- a/src/librustc/arena.rs
+++ b/src/librustc/arena.rs
@@ -23,17 +23,17 @@ macro_rules! arena_types {
             [] generics: rustc::ty::Generics,
             [] trait_def: rustc::ty::TraitDef,
             [] adt_def: rustc::ty::AdtDef,
-            [] steal_mir: rustc::ty::steal::Steal<rustc::mir::Body<$tcx>>,
-            [] mir: rustc::mir::Body<$tcx>,
+            [] steal_mir: rustc::ty::steal::Steal<rustc::mir::BodyCache<$tcx>>,
+            [] mir: rustc::mir::BodyCache<$tcx>,
             [] steal_promoted: rustc::ty::steal::Steal<
                 rustc_index::vec::IndexVec<
                     rustc::mir::Promoted,
-                    rustc::mir::Body<$tcx>
+                    rustc::mir::BodyCache<$tcx>
                 >
             >,
             [] promoted: rustc_index::vec::IndexVec<
                 rustc::mir::Promoted,
-                rustc::mir::Body<$tcx>
+                rustc::mir::BodyCache<$tcx>
             >,
             [] tables: rustc::ty::TypeckTables<$tcx>,
             [] const_allocs: rustc::mir::interpret::Allocation,
diff --git a/src/librustc/mir/cache.rs b/src/librustc/mir/cache.rs
index 9b413667418..b8ef4f753f3 100644
--- a/src/librustc/mir/cache.rs
+++ b/src/librustc/mir/cache.rs
@@ -1,16 +1,19 @@
 use rustc_index::vec::IndexVec;
-use rustc_data_structures::sync::{RwLock, MappedReadGuard, ReadGuard};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 use crate::ich::StableHashingContext;
-use crate::mir::{Body, BasicBlock};
+use crate::mir::{BasicBlock, BasicBlockData, Body, LocalDecls, Location, Successors};
+use rustc_data_structures::graph::{self, GraphPredecessors, GraphSuccessors};
+use rustc_data_structures::graph::dominators::{dominators, Dominators};
+use std::iter;
+use std::ops::{Deref, DerefMut, Index, IndexMut};
+use std::vec::IntoIter;
 
 #[derive(Clone, Debug)]
 pub struct Cache {
-    predecessors: RwLock<Option<IndexVec<BasicBlock, Vec<BasicBlock>>>>
+    predecessors: Option<IndexVec<BasicBlock, Vec<BasicBlock>>>,
 }
 
-
 impl rustc_serialize::Encodable for Cache {
     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
         Encodable::encode(&(), s)
@@ -31,39 +34,264 @@ impl<'a> HashStable<StableHashingContext<'a>> for Cache {
 
 impl Cache {
     pub fn new() -> Self {
-        Cache {
-            predecessors: RwLock::new(None)
+        Self {
+            predecessors: None,
         }
     }
 
-    pub fn invalidate(&self) {
+    pub fn invalidate_predecessors(&mut self) {
         // FIXME: consider being more fine-grained
-        *self.predecessors.borrow_mut() = None;
+        self.predecessors = None;
     }
 
-    pub fn predecessors(
-        &self,
-        body: &Body<'_>
-    ) -> MappedReadGuard<'_, IndexVec<BasicBlock, Vec<BasicBlock>>> {
-        if self.predecessors.borrow().is_none() {
-            *self.predecessors.borrow_mut() = Some(calculate_predecessors(body));
+    pub fn ensure_predecessors(&mut self, body: &Body<'_>) {
+        if self.predecessors.is_none() {
+            let mut result = IndexVec::from_elem(vec![], body.basic_blocks());
+            for (bb, data) in body.basic_blocks().iter_enumerated() {
+                if let Some(ref term) = data.terminator {
+                    for &tgt in term.successors() {
+                        result[tgt].push(bb);
+                    }
+                }
+            }
+
+            self.predecessors = Some(result)
         }
+    }
+
+    /// This will recompute the predecessors cache if it is not available
+    fn predecessors(&mut self, body: &Body<'_>) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
+        self.ensure_predecessors(body);
+        self.predecessors.as_ref().unwrap()
+    }
+
+    fn unwrap_predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
+        &self.predecessors.as_ref().unwrap()[bb]
+    }
 
-        ReadGuard::map(self.predecessors.borrow(), |p| p.as_ref().unwrap())
+    fn unwrap_predecessor_locations<'a>(
+        &'a self,
+        loc: Location,
+        body: &'a Body<'a>
+    ) -> impl Iterator<Item = Location> + 'a {
+        let if_zero_locations = if loc.statement_index == 0 {
+            let predecessor_blocks = self.unwrap_predecessors_for(loc.block);
+            let num_predecessor_blocks = predecessor_blocks.len();
+            Some(
+                (0..num_predecessor_blocks)
+                    .map(move |i| predecessor_blocks[i])
+                    .map(move |bb| body.terminator_loc(bb)),
+            )
+        } else {
+            None
+        };
+
+        let if_not_zero_locations = if loc.statement_index == 0 {
+            None
+        } else {
+            Some(Location { block: loc.block, statement_index: loc.statement_index - 1 })
+        };
+
+        if_zero_locations.into_iter().flatten().chain(if_not_zero_locations)
+    }
+
+    pub fn basic_blocks_mut<'a, 'tcx>(
+        &mut self,
+        body: &'a mut Body<'tcx>
+    ) -> &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
+        debug!("bbm: Clearing predecessors cache for body at: {:?}", body.span.data());
+        self.invalidate_predecessors();
+        &mut body.basic_blocks
+    }
+
+    pub fn basic_blocks_and_local_decls_mut<'a, 'tcx>(
+        &mut self,
+        body: &'a mut Body<'tcx>
+    ) -> (&'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &'a mut LocalDecls<'tcx>) {
+        debug!("bbaldm: Clearing predecessors cache for body at: {:?}", body.span.data());
+        self.invalidate_predecessors();
+        (&mut body.basic_blocks, &mut body.local_decls)
     }
 }
 
-fn calculate_predecessors(body: &Body<'_>) -> IndexVec<BasicBlock, Vec<BasicBlock>> {
-    let mut result = IndexVec::from_elem(vec![], body.basic_blocks());
-    for (bb, data) in body.basic_blocks().iter_enumerated() {
-        if let Some(ref term) = data.terminator {
-            for &tgt in term.successors() {
-                result[tgt].push(bb);
-            }
+#[derive(Clone, Debug, HashStable, RustcEncodable, RustcDecodable, TypeFoldable)]
+pub struct BodyCache<'tcx> {
+    cache: Cache,
+    body: Body<'tcx>,
+}
+
+impl BodyCache<'tcx> {
+    pub fn new(body: Body<'tcx>) -> Self {
+        Self {
+            cache: Cache::new(),
+            body,
+        }
+    }
+}
+
+#[macro_export]
+macro_rules! read_only {
+    ($body:expr) => {
+        {
+            $body.ensure_predecessors();
+            $body.unwrap_read_only()
+        }
+    };
+}
+
+impl BodyCache<'tcx> {
+    pub fn ensure_predecessors(&mut self) {
+        self.cache.ensure_predecessors(&self.body);
+    }
+
+    pub fn predecessors(&mut self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
+        self.cache.predecessors(&self.body)
+    }
+
+    pub fn unwrap_read_only(&self) -> ReadOnlyBodyCache<'_, 'tcx> {
+        ReadOnlyBodyCache::new(&self.cache, &self.body)
+    }
+
+    pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
+        self.cache.basic_blocks_mut(&mut self.body)
+    }
+
+    pub fn basic_blocks_and_local_decls_mut(
+        &mut self
+    ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
+        self.cache.basic_blocks_and_local_decls_mut(&mut self.body)
+    }
+}
+
+impl<'tcx> Index<BasicBlock> for BodyCache<'tcx> {
+    type Output = BasicBlockData<'tcx>;
+
+    fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
+        &self.body[index]
+    }
+}
+
+impl<'tcx> IndexMut<BasicBlock> for BodyCache<'tcx> {
+    fn index_mut(&mut self, index: BasicBlock) -> &mut Self::Output {
+        &mut self.basic_blocks_mut()[index]
+    }
+}
+
+impl<'tcx> Deref for BodyCache<'tcx> {
+    type Target = Body<'tcx>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.body
+    }
+}
+
+impl<'tcx> DerefMut for BodyCache<'tcx> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.body
+    }
+}
+
+#[derive(Copy, Clone, Debug)]
+pub struct ReadOnlyBodyCache<'a, 'tcx> {
+    cache: &'a Cache,
+    body: &'a Body<'tcx>,
+}
+
+impl ReadOnlyBodyCache<'a, 'tcx> {
+    fn new(cache: &'a Cache, body: &'a Body<'tcx>) -> Self {
+        assert!(
+            cache.predecessors.is_some(),
+            "Cannot construct ReadOnlyBodyCache without computed predecessors");
+        Self {
+            cache,
+            body,
         }
     }
 
-    result
+    pub fn predecessors(&self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
+        self.cache.predecessors.as_ref().unwrap()
+    }
+
+    pub fn predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
+        self.cache.unwrap_predecessors_for(bb)
+    }
+
+    pub fn predecessor_locations(&self, loc: Location) -> impl Iterator<Item = Location> + '_ {
+        self.cache.unwrap_predecessor_locations(loc, self.body)
+    }
+
+    pub fn body(&self) -> &'a Body<'tcx> {
+        self.body
+    }
+
+    pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
+        &self.body.basic_blocks
+    }
+
+    pub fn dominators(&self) -> Dominators<BasicBlock> {
+        dominators(self)
+    }
+}
+
+impl graph::DirectedGraph for ReadOnlyBodyCache<'a, 'tcx> {
+    type Node = BasicBlock;
+}
+
+impl graph::GraphPredecessors<'graph> for ReadOnlyBodyCache<'a, 'tcx> {
+    type Item = BasicBlock;
+    type Iter = IntoIter<BasicBlock>;
+}
+
+impl graph::WithPredecessors for ReadOnlyBodyCache<'a, 'tcx> {
+    fn predecessors(
+        &self,
+        node: Self::Node,
+    ) -> <Self as GraphPredecessors<'_>>::Iter {
+        self.cache.unwrap_predecessors_for(node).to_vec().into_iter()
+    }
+}
+
+impl graph::WithNumNodes for ReadOnlyBodyCache<'a, 'tcx> {
+    fn num_nodes(&self) -> usize {
+        self.body.num_nodes()
+    }
+}
+
+impl graph::WithStartNode for ReadOnlyBodyCache<'a, 'tcx> {
+    fn start_node(&self) -> Self::Node {
+        self.body.start_node()
+    }
+}
+
+impl graph::WithSuccessors for ReadOnlyBodyCache<'a, 'tcx> {
+    fn successors(
+        &self,
+        node: Self::Node,
+    ) -> <Self as GraphSuccessors<'_>>::Iter {
+        self.body.successors(node)
+    }
+}
+
+impl<'a, 'b, 'tcx> graph::GraphSuccessors<'b> for ReadOnlyBodyCache<'a, 'tcx> {
+    type Item = BasicBlock;
+    type Iter = iter::Cloned<Successors<'b>>;
+}
+
+
+impl Deref for ReadOnlyBodyCache<'a, 'tcx> {
+    type Target = Body<'tcx>;
+
+    fn deref(&self) -> &Self::Target {
+        self.body
+    }
+}
+
+impl Index<BasicBlock> for ReadOnlyBodyCache<'a, 'tcx> {
+    type Output = BasicBlockData<'tcx>;
+
+    fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
+        &self.body[index]
+    }
 }
 
 CloneTypeFoldableAndLiftImpls! {
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index 300b0363e2d..df5d4997e08 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -21,25 +21,25 @@ use crate::ty::{
 use polonius_engine::Atom;
 use rustc_index::bit_set::BitMatrix;
 use rustc_data_structures::fx::FxHashSet;
-use rustc_data_structures::graph::dominators::{dominators, Dominators};
-use rustc_data_structures::graph::{self, GraphPredecessors, GraphSuccessors};
+use rustc_data_structures::graph::dominators::Dominators;
+use rustc_data_structures::graph::{self, GraphSuccessors};
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_data_structures::sync::Lrc;
-use rustc_data_structures::sync::MappedReadGuard;
 use rustc_macros::HashStable;
 use rustc_serialize::{Encodable, Decodable};
 use smallvec::SmallVec;
 use std::borrow::Cow;
 use std::fmt::{self, Debug, Display, Formatter, Write};
-use std::ops::{Index, IndexMut};
+use std::ops::Index;
 use std::slice;
-use std::vec::IntoIter;
 use std::{iter, mem, option, u32};
 use syntax::ast::Name;
 use syntax::symbol::Symbol;
 use syntax_pos::{Span, DUMMY_SP};
 
 pub use crate::mir::interpret::AssertMessage;
+pub use crate::mir::cache::{BodyCache, ReadOnlyBodyCache};
+pub use crate::read_only;
 
 mod cache;
 pub mod interpret;
@@ -108,7 +108,7 @@ pub struct Body<'tcx> {
     pub yield_ty: Option<Ty<'tcx>>,
 
     /// Generator drop glue.
-    pub generator_drop: Option<Box<Body<'tcx>>>,
+    pub generator_drop: Option<Box<BodyCache<'tcx>>>,
 
     /// The layout of a generator. Produced by the state transformation.
     pub generator_layout: Option<GeneratorLayout<'tcx>>,
@@ -154,9 +154,6 @@ pub struct Body<'tcx> {
 
     /// A span representing this MIR, for error reporting.
     pub span: Span,
-
-    /// A cache for various calculations.
-    cache: cache::Cache,
 }
 
 impl<'tcx> Body<'tcx> {
@@ -193,7 +190,6 @@ impl<'tcx> Body<'tcx> {
             spread_arg: None,
             var_debug_info,
             span,
-            cache: cache::Cache::new(),
             control_flow_destroyed,
         }
     }
@@ -203,58 +199,6 @@ impl<'tcx> Body<'tcx> {
         &self.basic_blocks
     }
 
-    #[inline]
-    pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
-        self.cache.invalidate();
-        &mut self.basic_blocks
-    }
-
-    #[inline]
-    pub fn basic_blocks_and_local_decls_mut(
-        &mut self,
-    ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
-        self.cache.invalidate();
-        (&mut self.basic_blocks, &mut self.local_decls)
-    }
-
-    #[inline]
-    pub fn predecessors(&self) -> MappedReadGuard<'_, IndexVec<BasicBlock, Vec<BasicBlock>>> {
-        self.cache.predecessors(self)
-    }
-
-    #[inline]
-    pub fn predecessors_for(&self, bb: BasicBlock) -> MappedReadGuard<'_, Vec<BasicBlock>> {
-        MappedReadGuard::map(self.predecessors(), |p| &p[bb])
-    }
-
-    #[inline]
-    pub fn predecessor_locations(&self, loc: Location) -> impl Iterator<Item = Location> + '_ {
-        let if_zero_locations = if loc.statement_index == 0 {
-            let predecessor_blocks = self.predecessors_for(loc.block);
-            let num_predecessor_blocks = predecessor_blocks.len();
-            Some(
-                (0..num_predecessor_blocks)
-                    .map(move |i| predecessor_blocks[i])
-                    .map(move |bb| self.terminator_loc(bb)),
-            )
-        } else {
-            None
-        };
-
-        let if_not_zero_locations = if loc.statement_index == 0 {
-            None
-        } else {
-            Some(Location { block: loc.block, statement_index: loc.statement_index - 1 })
-        };
-
-        if_zero_locations.into_iter().flatten().chain(if_not_zero_locations)
-    }
-
-    #[inline]
-    pub fn dominators(&self) -> Dominators<BasicBlock> {
-        dominators(self)
-    }
-
     /// Returns `true` if a cycle exists in the control-flow graph that is reachable from the
     /// `START_BLOCK`.
     pub fn is_cfg_cyclic(&self) -> bool {
@@ -355,7 +299,7 @@ impl<'tcx> Body<'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_statement_nop(&mut self, location: Location) {
-        let block = &mut self[location.block];
+        let block = &mut self.basic_blocks[location.block];
         debug_assert!(location.statement_index < block.statements.len());
         block.statements[location.statement_index].make_nop()
     }
@@ -415,13 +359,6 @@ impl<'tcx> Index<BasicBlock> for Body<'tcx> {
     }
 }
 
-impl<'tcx> IndexMut<BasicBlock> for Body<'tcx> {
-    #[inline]
-    fn index_mut(&mut self, index: BasicBlock) -> &mut BasicBlockData<'tcx> {
-        &mut self.basic_blocks_mut()[index]
-    }
-}
-
 #[derive(Copy, Clone, Debug, HashStable, TypeFoldable)]
 pub enum ClearCrossCrate<T> {
     Clear,
@@ -2618,15 +2555,6 @@ impl<'tcx> graph::WithStartNode for Body<'tcx> {
     }
 }
 
-impl<'tcx> graph::WithPredecessors for Body<'tcx> {
-    fn predecessors(
-        &self,
-        node: Self::Node,
-    ) -> <Self as GraphPredecessors<'_>>::Iter {
-        self.predecessors_for(node).clone().into_iter()
-    }
-}
-
 impl<'tcx> graph::WithSuccessors for Body<'tcx> {
     fn successors(
         &self,
@@ -2636,11 +2564,6 @@ impl<'tcx> graph::WithSuccessors for Body<'tcx> {
     }
 }
 
-impl<'a, 'b> graph::GraphPredecessors<'b> for Body<'a> {
-    type Item = BasicBlock;
-    type Iter = IntoIter<BasicBlock>;
-}
-
 impl<'a, 'b> graph::GraphSuccessors<'b> for Body<'a> {
     type Item = BasicBlock;
     type Iter = iter::Cloned<Successors<'b>>;
@@ -2675,7 +2598,11 @@ impl Location {
     }
 
     /// Returns `true` if `other` is earlier in the control flow graph than `self`.
-    pub fn is_predecessor_of<'tcx>(&self, other: Location, body: &Body<'tcx>) -> bool {
+    pub fn is_predecessor_of<'tcx>(
+        &self,
+        other: Location,
+        body: ReadOnlyBodyCache<'_, 'tcx>
+    ) -> bool {
         // If we are in the same block as the other location and are an earlier statement
         // then we are a predecessor of `other`.
         if self.block == other.block && self.statement_index < other.statement_index {
@@ -2683,13 +2610,13 @@ impl Location {
         }
 
         // If we're in another block, then we want to check that block is a predecessor of `other`.
-        let mut queue: Vec<BasicBlock> = body.predecessors_for(other.block).clone();
+        let mut queue: Vec<BasicBlock> = body.predecessors_for(other.block).to_vec();
         let mut visited = FxHashSet::default();
 
         while let Some(block) = queue.pop() {
             // If we haven't visited this block before, then make sure we visit it's predecessors.
             if visited.insert(block) {
-                queue.append(&mut body.predecessors_for(block).clone());
+                queue.extend(body.predecessors_for(block).iter().cloned());
             } else {
                 continue;
             }
diff --git a/src/librustc/mir/visit.rs b/src/librustc/mir/visit.rs
index 145593f1c4d..47a1d67d5d6 100644
--- a/src/librustc/mir/visit.rs
+++ b/src/librustc/mir/visit.rs
@@ -65,13 +65,25 @@ use syntax_pos::Span;
 // variant argument) that does not require visiting, as in
 // `is_cleanup` above.
 
+macro_rules! body_cache_type {
+    (mut $a:lifetime, $tcx:lifetime) => {
+        &mut BodyCache<$tcx>
+    };
+    ($a:lifetime, $tcx:lifetime) => {
+        ReadOnlyBodyCache<$a, $tcx>
+    };
+}
+
 macro_rules! make_mir_visitor {
     ($visitor_trait_name:ident, $($mutability:ident)?) => {
         pub trait $visitor_trait_name<'tcx> {
             // Override these, and call `self.super_xxx` to revert back to the
             // default behavior.
 
-            fn visit_body(&mut self, body: & $($mutability)? Body<'tcx>) {
+            fn visit_body(
+                &mut self,
+                body: body_cache_type!($($mutability)? '_, 'tcx)
+            ) {
                 self.super_body(body);
             }
 
@@ -240,11 +252,14 @@ macro_rules! make_mir_visitor {
             // The `super_xxx` methods comprise the default behavior and are
             // not meant to be overridden.
 
-            fn super_body(&mut self,
-                         body: & $($mutability)? Body<'tcx>) {
+            fn super_body(
+                &mut self,
+                $($mutability)? body: body_cache_type!($($mutability)? '_, 'tcx)
+            ) {
+                let span = body.span;
                 if let Some(yield_ty) = &$($mutability)? body.yield_ty {
                     self.visit_ty(yield_ty, TyContext::YieldTy(SourceInfo {
-                        span: body.span,
+                        span,
                         scope: OUTERMOST_SOURCE_SCOPE,
                     }));
                 }
@@ -260,6 +275,7 @@ macro_rules! make_mir_visitor {
                     self.visit_basic_block_data(bb, data);
                 }
 
+                let body: & $($mutability)? Body<'_> = & $($mutability)? body;
                 for scope in &$($mutability)? body.source_scopes {
                     self.visit_source_scope_data(scope);
                 }
@@ -790,7 +806,11 @@ macro_rules! make_mir_visitor {
 
             // Convenience methods
 
-            fn visit_location(&mut self, body: & $($mutability)? Body<'tcx>, location: Location) {
+            fn visit_location(
+                &mut self,
+                body: body_cache_type!($($mutability)? '_, 'tcx),
+                location: Location
+            ) {
                 let basic_block = & $($mutability)? body[location.block];
                 if basic_block.statements.len() == location.statement_index {
                     if let Some(ref $($mutability)? terminator) = basic_block.terminator {
diff --git a/src/librustc/query/mod.rs b/src/librustc/query/mod.rs
index d715ddb1b81..a6d7e5c9291 100644
--- a/src/librustc/query/mod.rs
+++ b/src/librustc/query/mod.rs
@@ -106,44 +106,54 @@ rustc_queries! {
 
         /// Fetch the MIR for a given `DefId` right after it's built - this includes
         /// unreachable code.
-        query mir_built(_: DefId) -> &'tcx Steal<mir::Body<'tcx>> {}
+        query mir_built(_: DefId) -> &'tcx Steal<mir::BodyCache<'tcx>> {}
 
         /// Fetch the MIR for a given `DefId` up till the point where it is
         /// ready for const evaluation.
         ///
         /// See the README for the `mir` module for details.
-        query mir_const(_: DefId) -> &'tcx Steal<mir::Body<'tcx>> {
+        query mir_const(_: DefId) -> &'tcx Steal<mir::BodyCache<'tcx>> {
             no_hash
         }
 
         query mir_validated(_: DefId) ->
             (
-                &'tcx Steal<mir::Body<'tcx>>,
-                &'tcx Steal<IndexVec<mir::Promoted, mir::Body<'tcx>>>
+                &'tcx Steal<mir::BodyCache<'tcx>>,
+                &'tcx Steal<IndexVec<mir::Promoted, mir::BodyCache<'tcx>>>
             ) {
             no_hash
         }
 
         /// MIR after our optimization passes have run. This is MIR that is ready
         /// for codegen. This is also the only query that can fetch non-local MIR, at present.
-        query optimized_mir(key: DefId) -> &'tcx mir::Body<'tcx> {
+        query optimized_mir(key: DefId) -> &'tcx mir::BodyCache<'tcx> {
             cache_on_disk_if { key.is_local() }
             load_cached(tcx, id) {
-                let mir: Option<crate::mir::Body<'tcx>> = tcx.queries.on_disk_cache
-                                                            .try_load_query_result(tcx, id);
-                mir.map(|x| &*tcx.arena.alloc(x))
+                let mir: Option<crate::mir::BodyCache<'tcx>>
+                    = tcx.queries.on_disk_cache.try_load_query_result(tcx, id);
+                mir.map(|x| {
+                    let cache = tcx.arena.alloc(x);
+                    cache.ensure_predecessors();
+                    &*cache
+                })
             }
         }
 
-        query promoted_mir(key: DefId) -> &'tcx IndexVec<mir::Promoted, mir::Body<'tcx>> {
+        query promoted_mir(key: DefId) -> &'tcx IndexVec<mir::Promoted, mir::BodyCache<'tcx>> {
             cache_on_disk_if { key.is_local() }
             load_cached(tcx, id) {
                 let promoted: Option<
                     rustc_index::vec::IndexVec<
                         crate::mir::Promoted,
-                        crate::mir::Body<'tcx>
+                        crate::mir::BodyCache<'tcx>
                     >> = tcx.queries.on_disk_cache.try_load_query_result(tcx, id);
-                promoted.map(|p| &*tcx.arena.alloc(p))
+                promoted.map(|p| {
+                    let cache = tcx.arena.alloc(p);
+                    for body in cache.iter_mut() {
+                        body.ensure_predecessors();
+                    }
+                    &*cache
+                })
             }
         }
     }
@@ -502,7 +512,7 @@ rustc_queries! {
         /// in the case of closures, this will be redirected to the enclosing function.
         query region_scope_tree(_: DefId) -> &'tcx region::ScopeTree {}
 
-        query mir_shims(key: ty::InstanceDef<'tcx>) -> &'tcx mir::Body<'tcx> {
+        query mir_shims(key: ty::InstanceDef<'tcx>) -> &'tcx mir::BodyCache<'tcx> {
             no_force
             desc { |tcx| "generating MIR shim for `{}`", tcx.def_path_str(key.def_id()) }
         }
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 776ae7dc141..6a0002cd80f 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -22,7 +22,7 @@ use crate::middle::cstore::EncodedMetadata;
 use crate::middle::lang_items;
 use crate::middle::resolve_lifetime::{self, ObjectLifetimeDefault};
 use crate::middle::stability;
-use crate::mir::{Body, Field, interpret, Local, Place, PlaceElem, ProjectionKind, Promoted};
+use crate::mir::{BodyCache, Field, interpret, Local, Place, PlaceElem, ProjectionKind, Promoted};
 use crate::mir::interpret::{ConstValue, Allocation, Scalar};
 use crate::ty::subst::{GenericArg, InternalSubsts, SubstsRef, Subst};
 use crate::ty::ReprOptions;
@@ -1083,17 +1083,17 @@ impl<'tcx> TyCtxt<'tcx> {
         &self.hir_map
     }
 
-    pub fn alloc_steal_mir(self, mir: Body<'tcx>) -> &'tcx Steal<Body<'tcx>> {
+    pub fn alloc_steal_mir(self, mir: BodyCache<'tcx>) -> &'tcx Steal<BodyCache<'tcx>> {
         self.arena.alloc(Steal::new(mir))
     }
 
-    pub fn alloc_steal_promoted(self, promoted: IndexVec<Promoted, Body<'tcx>>) ->
-        &'tcx Steal<IndexVec<Promoted, Body<'tcx>>> {
+    pub fn alloc_steal_promoted(self, promoted: IndexVec<Promoted, BodyCache<'tcx>>) ->
+        &'tcx Steal<IndexVec<Promoted, BodyCache<'tcx>>> {
         self.arena.alloc(Steal::new(promoted))
     }
 
-    pub fn intern_promoted(self, promoted: IndexVec<Promoted, Body<'tcx>>) ->
-        &'tcx IndexVec<Promoted, Body<'tcx>> {
+    pub fn intern_promoted(self, promoted: IndexVec<Promoted, BodyCache<'tcx>>) ->
+        &'tcx IndexVec<Promoted, BodyCache<'tcx>> {
         self.arena.alloc(promoted)
     }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 8ccfc467f4a..c9a934e9ebd 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -18,7 +18,7 @@ use crate::infer::canonical::Canonical;
 use crate::middle::cstore::CrateStoreDyn;
 use crate::middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
 use crate::middle::resolve_lifetime::ObjectLifetimeDefault;
-use crate::mir::Body;
+use crate::mir::ReadOnlyBodyCache;
 use crate::mir::interpret::{GlobalId, ErrorHandled};
 use crate::mir::GeneratorLayout;
 use crate::session::CrateDisambiguator;
@@ -2985,10 +2985,10 @@ impl<'tcx> TyCtxt<'tcx> {
     }
 
     /// Returns the possibly-auto-generated MIR of a `(DefId, Subst)` pair.
-    pub fn instance_mir(self, instance: ty::InstanceDef<'tcx>) -> &'tcx Body<'tcx> {
+    pub fn instance_mir(self, instance: ty::InstanceDef<'tcx>) -> ReadOnlyBodyCache<'tcx, 'tcx> {
         match instance {
             ty::InstanceDef::Item(did) => {
-                self.optimized_mir(did)
+                self.optimized_mir(did).unwrap_read_only()
             }
             ty::InstanceDef::VtableShim(..) |
             ty::InstanceDef::ReifyShim(..) |
@@ -2998,7 +2998,7 @@ impl<'tcx> TyCtxt<'tcx> {
             ty::InstanceDef::ClosureOnceShim { .. } |
             ty::InstanceDef::DropGlue(..) |
             ty::InstanceDef::CloneShim(..) => {
-                self.mir_shims(instance)
+                self.mir_shims(instance).unwrap_read_only()
             }
         }
     }
diff --git a/src/librustc_codegen_ssa/base.rs b/src/librustc_codegen_ssa/base.rs
index 22693beb855..e460a4a2e8c 100644
--- a/src/librustc_codegen_ssa/base.rs
+++ b/src/librustc_codegen_ssa/base.rs
@@ -374,7 +374,7 @@ pub fn codegen_instance<'a, 'tcx: 'a, Bx: BuilderMethods<'a, 'tcx>>(
     let lldecl = cx.get_fn(instance);
 
     let mir = cx.tcx().instance_mir(instance.def);
-    mir::codegen_mir::<Bx>(cx, lldecl, &mir, instance, sig);
+    mir::codegen_mir::<Bx>(cx, lldecl, mir, instance, sig);
 }
 
 /// Creates the `main` function which will initialize the rust runtime and call
diff --git a/src/librustc_codegen_ssa/mir/analyze.rs b/src/librustc_codegen_ssa/mir/analyze.rs
index e44551fcbcd..f15456e0ff8 100644
--- a/src/librustc_codegen_ssa/mir/analyze.rs
+++ b/src/librustc_codegen_ssa/mir/analyze.rs
@@ -29,7 +29,7 @@ pub fn non_ssa_locals<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         // FIXME(eddyb): We should figure out how to use llvm.dbg.value instead
         // of putting everything in allocas just so we can use llvm.dbg.declare.
         if fx.cx.sess().opts.debuginfo == DebugInfo::Full {
-            if mir.local_kind(local) == mir::LocalKind::Arg {
+            if fx.mir.local_kind(local) == mir::LocalKind::Arg {
                 analyzer.not_ssa(local);
                 continue;
             }
@@ -70,9 +70,10 @@ impl<Bx: BuilderMethods<'a, 'tcx>> LocalAnalyzer<'mir, 'a, 'tcx, Bx> {
     fn new(fx: &'mir FunctionCx<'a, 'tcx, Bx>) -> Self {
         let invalid_location =
             mir::BasicBlock::new(fx.mir.basic_blocks().len()).start_location();
+        let dominators = fx.mir.dominators();
         let mut analyzer = LocalAnalyzer {
             fx,
-            dominators: fx.mir.dominators(),
+            dominators,
             non_ssa_locals: BitSet::new_empty(fx.mir.local_decls.len()),
             first_assignment: IndexVec::from_elem(invalid_location, &fx.mir.local_decls)
         };
@@ -130,7 +131,7 @@ impl<Bx: BuilderMethods<'a, 'tcx>> LocalAnalyzer<'mir, 'a, 'tcx, Bx> {
             };
             if is_consume {
                 let base_ty =
-                    mir::Place::ty_from(place_ref.base, proj_base, self.fx.mir, cx.tcx());
+                    mir::Place::ty_from(place_ref.base, proj_base, &*self.fx.mir, cx.tcx());
                 let base_ty = self.fx.monomorphize(&base_ty);
 
                 // ZSTs don't require any actual memory access.
diff --git a/src/librustc_codegen_ssa/mir/block.rs b/src/librustc_codegen_ssa/mir/block.rs
index d76392f7570..23a5b0cf32a 100644
--- a/src/librustc_codegen_ssa/mir/block.rs
+++ b/src/librustc_codegen_ssa/mir/block.rs
@@ -153,7 +153,7 @@ impl<'a, 'tcx> TerminatorCodegenHelper<'a, 'tcx> {
     // a loop.
     fn maybe_sideeffect<'b, 'tcx2: 'b, Bx: BuilderMethods<'b, 'tcx2>>(
         &self,
-        mir: &'b mir::Body<'tcx>,
+        mir: mir::ReadOnlyBodyCache<'b, 'tcx>,
         bx: &mut Bx,
         targets: &[mir::BasicBlock],
     ) {
@@ -324,7 +324,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
         target: mir::BasicBlock,
         unwind: Option<mir::BasicBlock>,
     ) {
-        let ty = location.ty(self.mir, bx.tcx()).ty;
+        let ty = location.ty(&*self.mir, bx.tcx()).ty;
         let ty = self.monomorphize(&ty);
         let drop_fn = Instance::resolve_drop_in_place(bx.tcx(), ty);
 
@@ -510,7 +510,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
 
         let extra_args = &args[sig.inputs().len()..];
         let extra_args = extra_args.iter().map(|op_arg| {
-            let op_ty = op_arg.ty(self.mir, bx.tcx());
+            let op_ty = op_arg.ty(&*self.mir, bx.tcx());
             self.monomorphize(&op_ty)
         }).collect::<Vec<_>>();
 
@@ -569,7 +569,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                 // a NOP
                 let target = destination.as_ref().unwrap().1;
                 helper.maybe_sideeffect(self.mir, &mut bx, &[target]);
-                helper.funclet_br(self, &mut bx, target);
+                helper.funclet_br(self, &mut bx, target)
             }
             return;
         }
@@ -791,7 +791,8 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
         bb: mir::BasicBlock,
     ) {
         let mut bx = self.build_block(bb);
-        let data = &self.mir[bb];
+        let mir = self.mir;
+        let data = &mir[bb];
 
         debug!("codegen_block({:?}={:?})", bb, data);
 
@@ -1050,7 +1051,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
 
     fn landing_pad_uncached(
         &mut self,
-        target_bb: Bx::BasicBlock
+        target_bb: Bx::BasicBlock,
     ) -> Bx::BasicBlock {
         if base::wants_msvc_seh(self.cx.sess()) {
             span_bug!(self.mir.span, "landing pad was not inserted?")
diff --git a/src/librustc_codegen_ssa/mir/mod.rs b/src/librustc_codegen_ssa/mir/mod.rs
index 6041232489d..8b60904081e 100644
--- a/src/librustc_codegen_ssa/mir/mod.rs
+++ b/src/librustc_codegen_ssa/mir/mod.rs
@@ -1,6 +1,6 @@
 use rustc::ty::{self, Ty, TypeFoldable, Instance};
 use rustc::ty::layout::{TyLayout, HasTyCtxt, FnAbiExt};
-use rustc::mir::{self, Body};
+use rustc::mir::{self, Body, ReadOnlyBodyCache};
 use rustc_target::abi::call::{FnAbi, PassMode};
 use crate::base;
 use crate::traits::*;
@@ -21,7 +21,7 @@ use self::operand::{OperandRef, OperandValue};
 pub struct FunctionCx<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> {
     instance: Instance<'tcx>,
 
-    mir: &'a mir::Body<'tcx>,
+    mir: mir::ReadOnlyBodyCache<'a, 'tcx>,
 
     debug_context: Option<FunctionDebugContext<Bx::DIScope>>,
 
@@ -122,7 +122,7 @@ impl<'a, 'tcx, V: CodegenObject> LocalRef<'tcx, V> {
 pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     cx: &'a Bx::CodegenCx,
     llfn: Bx::Function,
-    mir: &'a Body<'tcx>,
+    mir: ReadOnlyBodyCache<'a, 'tcx>,
     instance: Instance<'tcx>,
     sig: ty::FnSig<'tcx>,
 ) {
@@ -132,7 +132,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     debug!("fn_abi: {:?}", fn_abi);
 
     let debug_context =
-        cx.create_function_debug_context(instance, sig, llfn, mir);
+        cx.create_function_debug_context(instance, sig, llfn, &mir);
 
     let mut bx = Bx::new_block(cx, llfn, "start");
 
@@ -155,8 +155,8 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
             }
         }).collect();
 
-    let (landing_pads, funclets) = create_funclets(mir, &mut bx, &cleanup_kinds, &block_bxs);
-
+    let (landing_pads, funclets) = create_funclets(&mir, &mut bx, &cleanup_kinds, &block_bxs);
+    let mir_body: &Body<'_> = mir.body();
     let mut fx = FunctionCx {
         instance,
         mir,
@@ -171,7 +171,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         funclets,
         locals: IndexVec::new(),
         debug_context,
-        per_local_var_debug_info: debuginfo::per_local_var_debug_info(cx.tcx(), mir),
+        per_local_var_debug_info: debuginfo::per_local_var_debug_info(cx.tcx(), mir_body),
     };
 
     let memory_locals = analyze::non_ssa_locals(&fx);
@@ -181,7 +181,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         let args = arg_local_refs(&mut bx, &fx, &memory_locals);
 
         let mut allocate_local = |local| {
-            let decl = &mir.local_decls[local];
+            let decl = &mir_body.local_decls[local];
             let layout = bx.layout_of(fx.monomorphize(&decl.ty));
             assert!(!layout.ty.has_erasable_regions());
 
@@ -207,7 +207,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         let retptr = allocate_local(mir::RETURN_PLACE);
         iter::once(retptr)
             .chain(args.into_iter())
-            .chain(mir.vars_and_temps_iter().map(allocate_local))
+            .chain(mir_body.vars_and_temps_iter().map(allocate_local))
             .collect()
     };
 
@@ -226,8 +226,8 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         debug_context.source_locations_enabled = true;
     }
 
-    let rpo = traversal::reverse_postorder(&mir);
-    let mut visited = BitSet::new_empty(mir.basic_blocks().len());
+    let rpo = traversal::reverse_postorder(&mir_body);
+    let mut visited = BitSet::new_empty(mir_body.basic_blocks().len());
 
     // Codegen the body of each block using reverse postorder
     for (bb, _) in rpo {
@@ -237,7 +237,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
 
     // Remove blocks that haven't been visited, or have no
     // predecessors.
-    for bb in mir.basic_blocks().indices() {
+    for bb in mir_body.basic_blocks().indices() {
         // Unreachable block
         if !visited.contains(bb.index()) {
             debug!("codegen_mir: block {:?} was not visited", bb);
@@ -248,8 +248,8 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     }
 }
 
-fn create_funclets<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
-    mir: &'a Body<'tcx>,
+fn create_funclets<'a, 'b, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
+    mir: &'b Body<'tcx>,
     bx: &mut Bx,
     cleanup_kinds: &IndexVec<mir::BasicBlock, CleanupKind>,
     block_bxs: &IndexVec<mir::BasicBlock, Bx::BasicBlock>,
diff --git a/src/librustc_codegen_ssa/mir/place.rs b/src/librustc_codegen_ssa/mir/place.rs
index 4df5bce9537..9dd4d0ec22f 100644
--- a/src/librustc_codegen_ssa/mir/place.rs
+++ b/src/librustc_codegen_ssa/mir/place.rs
@@ -591,7 +591,12 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
 
     pub fn monomorphized_place_ty(&self, place_ref: &mir::PlaceRef<'_, 'tcx>) -> Ty<'tcx> {
         let tcx = self.cx.tcx();
-        let place_ty = mir::Place::ty_from(place_ref.base, place_ref.projection, self.mir, tcx);
+        let place_ty = mir::Place::ty_from(
+            place_ref.base,
+            place_ref.projection,
+            &*self.mir,
+            tcx,
+        );
         self.monomorphize(&place_ty.ty)
     }
 }
diff --git a/src/librustc_codegen_ssa/mir/rvalue.rs b/src/librustc_codegen_ssa/mir/rvalue.rs
index f7fb4a57140..3bae027e763 100644
--- a/src/librustc_codegen_ssa/mir/rvalue.rs
+++ b/src/librustc_codegen_ssa/mir/rvalue.rs
@@ -513,7 +513,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
             mir::Rvalue::Aggregate(..) => {
                 // According to `rvalue_creates_operand`, only ZST
                 // aggregate rvalues are allowed to be operands.
-                let ty = rvalue.ty(self.mir, self.cx.tcx());
+                let ty = rvalue.ty(&*self.mir, self.cx.tcx());
                 let operand = OperandRef::new_zst(
                     &mut bx,
                     self.cx.layout_of(self.monomorphize(&ty)),
@@ -710,7 +710,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                 true,
             mir::Rvalue::Repeat(..) |
             mir::Rvalue::Aggregate(..) => {
-                let ty = rvalue.ty(self.mir, self.cx.tcx());
+                let ty = rvalue.ty(&*self.mir, self.cx.tcx());
                 let ty = self.monomorphize(&ty);
                 self.cx.spanned_layout_of(ty, span).is_zst()
             }
diff --git a/src/librustc_data_structures/graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
index 444463c08e5..5fb58eea381 100644
--- a/src/librustc_data_structures/graph/dominators/mod.rs
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -7,32 +7,33 @@
 use rustc_index::vec::{Idx, IndexVec};
 use super::iterate::reverse_post_order;
 use super::ControlFlowGraph;
+use std::borrow::BorrowMut;
 
 #[cfg(test)]
 mod tests;
 
-pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
+pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> {
     let start_node = graph.start_node();
-    let rpo = reverse_post_order(graph, start_node);
+    let rpo = reverse_post_order(&graph, start_node);
     dominators_given_rpo(graph, &rpo)
 }
 
-fn dominators_given_rpo<G: ControlFlowGraph>(
-    graph: &G,
+fn dominators_given_rpo<G: ControlFlowGraph + BorrowMut<G>>(
+    mut graph: G,
     rpo: &[G::Node],
 ) -> Dominators<G::Node> {
-    let start_node = graph.start_node();
+    let start_node = graph.borrow().start_node();
     assert_eq!(rpo[0], start_node);
 
     // compute the post order index (rank) for each node
     let mut post_order_rank: IndexVec<G::Node, usize> =
-        (0..graph.num_nodes()).map(|_| 0).collect();
+        (0..graph.borrow().num_nodes()).map(|_| 0).collect();
     for (index, node) in rpo.iter().rev().cloned().enumerate() {
         post_order_rank[node] = index;
     }
 
     let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
-        (0..graph.num_nodes()).map(|_| None).collect();
+        (0..graph.borrow().num_nodes()).map(|_| None).collect();
     immediate_dominators[start_node] = Some(start_node);
 
     let mut changed = true;
@@ -41,7 +42,7 @@ fn dominators_given_rpo<G: ControlFlowGraph>(
 
         for &node in &rpo[1..] {
             let mut new_idom = None;
-            for pred in graph.predecessors(node) {
+            for pred in graph.borrow_mut().predecessors(node) {
                 if immediate_dominators[pred].is_some() {
                     // (*) dominators for `pred` have been calculated
                     new_idom = Some(if let Some(new_idom) = new_idom {
diff --git a/src/librustc_metadata/rmeta/decoder.rs b/src/librustc_metadata/rmeta/decoder.rs
index 820783bab6d..42db642cd4d 100644
--- a/src/librustc_metadata/rmeta/decoder.rs
+++ b/src/librustc_metadata/rmeta/decoder.rs
@@ -18,12 +18,11 @@ use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::svh::Svh;
 use rustc::dep_graph::{self, DepNodeIndex};
 use rustc::middle::lang_items;
-use rustc::mir::{self, interpret};
+use rustc::mir::{self, BodyCache, interpret, Promoted};
 use rustc::mir::interpret::{AllocDecodingSession, AllocDecodingState};
 use rustc::session::Session;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::codec::TyDecoder;
-use rustc::mir::{Body, Promoted};
 use rustc::util::common::record_time;
 use rustc::util::captures::Captures;
 
@@ -1080,26 +1079,32 @@ impl<'a, 'tcx> CrateMetadata {
             self.root.per_def.mir.get(self, id).is_some()
     }
 
-    fn get_optimized_mir(&self, tcx: TyCtxt<'tcx>, id: DefIndex) -> Body<'tcx> {
-        self.root.per_def.mir.get(self, id)
+    fn get_optimized_mir(&self, tcx: TyCtxt<'tcx>, id: DefIndex) -> BodyCache<'tcx> {
+        let mut cache = self.root.per_def.mir.get(self, id)
             .filter(|_| !self.is_proc_macro(id))
             .unwrap_or_else(|| {
                 bug!("get_optimized_mir: missing MIR for `{:?}`", self.local_def_id(id))
             })
-            .decode((self, tcx))
+            .decode((self, tcx));
+        cache.ensure_predecessors();
+        cache
     }
 
     fn get_promoted_mir(
         &self,
         tcx: TyCtxt<'tcx>,
         id: DefIndex,
-    ) -> IndexVec<Promoted, Body<'tcx>> {
-        self.root.per_def.promoted_mir.get(self, id)
+    ) -> IndexVec<Promoted, BodyCache<'tcx>> {
+        let mut cache = self.root.per_def.promoted_mir.get(self, id)
             .filter(|_| !self.is_proc_macro(id))
             .unwrap_or_else(|| {
                 bug!("get_promoted_mir: missing MIR for `{:?}`", self.local_def_id(id))
             })
-            .decode((self, tcx))
+            .decode((self, tcx));
+        for body in cache.iter_mut() {
+            body.ensure_predecessors();
+        }
+        cache
     }
 
     fn mir_const_qualif(&self, id: DefIndex) -> mir::ConstQualifs {
diff --git a/src/librustc_metadata/rmeta/mod.rs b/src/librustc_metadata/rmeta/mod.rs
index 4ea562fced3..fdf43f06eb1 100644
--- a/src/librustc_metadata/rmeta/mod.rs
+++ b/src/librustc_metadata/rmeta/mod.rs
@@ -276,8 +276,8 @@ define_per_def_tables! {
     // Also, as an optimization, a missing entry indicates an empty `&[]`.
     inferred_outlives: Table<DefIndex, Lazy!(&'tcx [(ty::Predicate<'tcx>, Span)])>,
     super_predicates: Table<DefIndex, Lazy!(ty::GenericPredicates<'tcx>)>,
-    mir: Table<DefIndex, Lazy!(mir::Body<'tcx>)>,
-    promoted_mir: Table<DefIndex, Lazy!(IndexVec<mir::Promoted, mir::Body<'tcx>>)>,
+    mir: Table<DefIndex, Lazy!(mir::BodyCache<'tcx>)>,
+    promoted_mir: Table<DefIndex, Lazy!(IndexVec<mir::Promoted, mir::BodyCache<'tcx>>)>,
 }
 
 #[derive(Copy, Clone, RustcEncodable, RustcDecodable)]
diff --git a/src/librustc_mir/borrow_check/borrow_set.rs b/src/librustc_mir/borrow_check/borrow_set.rs
index 94323431990..802464ce86b 100644
--- a/src/librustc_mir/borrow_check/borrow_set.rs
+++ b/src/librustc_mir/borrow_check/borrow_set.rs
@@ -5,7 +5,7 @@ use crate::dataflow::indexes::BorrowIndex;
 use crate::dataflow::move_paths::MoveData;
 use rustc::mir::traversal;
 use rustc::mir::visit::{PlaceContext, Visitor, NonUseContext, MutatingUseContext};
-use rustc::mir::{self, Location, Body, Local};
+use rustc::mir::{self, Location, Body, Local, ReadOnlyBodyCache};
 use rustc::ty::{RegionVid, TyCtxt};
 use rustc::util::nodemap::{FxHashMap, FxHashSet};
 use rustc_index::vec::IndexVec;
@@ -90,7 +90,7 @@ crate enum LocalsStateAtExit {
 impl LocalsStateAtExit {
     fn build(
         locals_are_invalidated_at_exit: bool,
-        body: &Body<'tcx>,
+        body: ReadOnlyBodyCache<'_, 'tcx>,
         move_data: &MoveData<'tcx>
     ) -> Self {
         struct HasStorageDead(BitSet<Local>);
@@ -106,7 +106,8 @@ impl LocalsStateAtExit {
         if locals_are_invalidated_at_exit {
             LocalsStateAtExit::AllAreInvalidated
         } else {
-            let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len()));
+            let mut has_storage_dead
+                = HasStorageDead(BitSet::new_empty(body.local_decls.len()));
             has_storage_dead.visit_body(body);
             let mut has_storage_dead_or_moved = has_storage_dead.0;
             for move_out in &move_data.moves {
@@ -123,13 +124,13 @@ impl LocalsStateAtExit {
 impl<'tcx> BorrowSet<'tcx> {
     pub fn build(
         tcx: TyCtxt<'tcx>,
-        body: &Body<'tcx>,
+        body: ReadOnlyBodyCache<'_, 'tcx>,
         locals_are_invalidated_at_exit: bool,
         move_data: &MoveData<'tcx>,
     ) -> Self {
         let mut visitor = GatherBorrows {
             tcx,
-            body,
+            body: &body,
             idx_vec: IndexVec::new(),
             location_map: Default::default(),
             activation_map: Default::default(),
@@ -139,7 +140,7 @@ impl<'tcx> BorrowSet<'tcx> {
                 LocalsStateAtExit::build(locals_are_invalidated_at_exit, body, move_data),
         };
 
-        for (block, block_data) in traversal::preorder(body) {
+        for (block, block_data) in traversal::preorder(&body) {
             visitor.visit_basic_block_data(block, block_data);
         }
 
diff --git a/src/librustc_mir/borrow_check/conflict_errors.rs b/src/librustc_mir/borrow_check/conflict_errors.rs
index 48f8ad9bbd8..73a9fd81c9b 100644
--- a/src/librustc_mir/borrow_check/conflict_errors.rs
+++ b/src/librustc_mir/borrow_check/conflict_errors.rs
@@ -205,9 +205,12 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 );
             }
 
-            let ty =
-                Place::ty_from(used_place.base, used_place.projection, self.body, self.infcx.tcx)
-                    .ty;
+            let ty = Place::ty_from(
+                used_place.base,
+                used_place.projection,
+                &*self.body,
+                self.infcx.tcx
+            ).ty;
             let needs_note = match ty.kind {
                 ty::Closure(id, _) => {
                     let tables = self.infcx.tcx.typeck_tables_of(id);
@@ -222,7 +225,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 let mpi = self.move_data.moves[move_out_indices[0]].path;
                 let place = &self.move_data.move_paths[mpi].place;
 
-                let ty = place.ty(self.body, self.infcx.tcx).ty;
+                let ty = place.ty(&*self.body, self.infcx.tcx).ty;
                 let opt_name =
                     self.describe_place_with_options(place.as_ref(), IncludingDowncast(true));
                 let note_msg = match opt_name {
@@ -314,7 +317,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             None,
         ).add_explanation_to_diagnostic(
             self.infcx.tcx,
-            self.body,
+            &self.body,
             &self.local_names,
             &mut err,
             "",
@@ -356,7 +359,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         self.explain_why_borrow_contains_point(location, borrow, None)
             .add_explanation_to_diagnostic(
                 self.infcx.tcx,
-                self.body,
+                &self.body,
                 &self.local_names,
                 &mut err,
                 "",
@@ -578,7 +581,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
 
         explanation.add_explanation_to_diagnostic(
             self.infcx.tcx,
-            self.body,
+            &self.body,
             &self.local_names,
             &mut err,
             first_borrow_desc,
@@ -619,7 +622,12 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         // Define a small closure that we can use to check if the type of a place
         // is a union.
         let union_ty = |place_base, place_projection| {
-            let ty = Place::ty_from(place_base, place_projection, self.body, self.infcx.tcx).ty;
+            let ty = Place::ty_from(
+                place_base,
+                place_projection,
+                &*self.body,
+                self.infcx.tcx
+            ).ty;
             ty.ty_adt_def().filter(|adt| adt.is_union()).map(|_| ty)
         };
         let describe_place = |place| self.describe_place(place).unwrap_or_else(|| "_".to_owned());
@@ -965,7 +973,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             } else {
                 explanation.add_explanation_to_diagnostic(
                     self.infcx.tcx,
-                    self.body,
+                    &self.body,
                     &self.local_names,
                     &mut err,
                     "",
@@ -991,7 +999,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             );
 
             explanation.add_explanation_to_diagnostic(
-                self.infcx.tcx, self.body, &self.local_names, &mut err, "", None);
+                self.infcx.tcx, &self.body, &self.local_names, &mut err, "", None);
         }
 
         err
@@ -1051,7 +1059,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
 
         explanation.add_explanation_to_diagnostic(
             self.infcx.tcx,
-            self.body,
+            &self.body,
             &self.local_names,
             &mut err,
             "",
@@ -1138,7 +1146,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         }
         explanation.add_explanation_to_diagnostic(
             self.infcx.tcx,
-            self.body,
+            &self.body,
             &self.local_names,
             &mut err,
             "",
@@ -1174,11 +1182,12 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         };
 
         // FIXME use a better heuristic than Spans
-        let reference_desc = if return_span == self.body.source_info(borrow.reserve_location).span {
-            "reference to"
-        } else {
-            "value referencing"
-        };
+        let reference_desc
+            = if return_span == self.body.source_info(borrow.reserve_location).span {
+                "reference to"
+            } else {
+                "value referencing"
+            };
 
         let (place_desc, note) = if let Some(place_desc) = opt_place_desc {
             let local_kind = if let Some(local) = borrow.borrowed_place.as_local() {
@@ -1372,10 +1381,8 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
     }
 
     fn get_moved_indexes(&mut self, location: Location, mpi: MovePathIndex) -> Vec<MoveSite> {
-        let body = self.body;
-
         let mut stack = Vec::new();
-        stack.extend(body.predecessor_locations(location).map(|predecessor| {
+        stack.extend(self.body.predecessor_locations(location).map(|predecessor| {
             let is_back_edge = location.dominates(predecessor, &self.dominators);
             (predecessor, is_back_edge)
         }));
@@ -1394,7 +1401,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             }
 
             // check for moves
-            let stmt_kind = body[location.block]
+            let stmt_kind = self.body[location.block]
                 .statements
                 .get(location.statement_index)
                 .map(|s| &s.kind);
@@ -1449,7 +1456,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             let mut any_match = false;
             drop_flag_effects::for_location_inits(
                 self.infcx.tcx,
-                self.body,
+                &self.body,
                 self.move_data,
                 location,
                 |m| {
@@ -1462,7 +1469,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 continue 'dfs;
             }
 
-            stack.extend(body.predecessor_locations(location).map(|predecessor| {
+            stack.extend(self.body.predecessor_locations(location).map(|predecessor| {
                 let back_edge = location.dominates(predecessor, &self.dominators);
                 (predecessor, is_back_edge || back_edge)
             }));
@@ -1514,7 +1521,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         self.explain_why_borrow_contains_point(location, loan, None)
             .add_explanation_to_diagnostic(
                 self.infcx.tcx,
-                self.body,
+                &self.body,
                 &self.local_names,
                 &mut err,
                 "",
@@ -1625,7 +1632,12 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                         StorageDeadOrDrop::LocalStorageDead
                         | StorageDeadOrDrop::BoxedStorageDead => {
                             assert!(
-                                Place::ty_from(&place.base, proj_base, self.body, tcx).ty.is_box(),
+                                Place::ty_from(
+                                    &place.base,
+                                    proj_base,
+                                    &*self.body,
+                                    tcx
+                                ).ty.is_box(),
                                 "Drop of value behind a reference or raw pointer"
                             );
                             StorageDeadOrDrop::BoxedStorageDead
@@ -1633,7 +1645,12 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                         StorageDeadOrDrop::Destructor(_) => base_access,
                     },
                     ProjectionElem::Field(..) | ProjectionElem::Downcast(..) => {
-                        let base_ty = Place::ty_from(&place.base, proj_base, self.body, tcx).ty;
+                        let base_ty = Place::ty_from(
+                            &place.base,
+                            proj_base,
+                            &*self.body,
+                            tcx
+                        ).ty;
                         match base_ty.kind {
                             ty::Adt(def, _) if def.has_dtor(tcx) => {
                                 // Report the outermost adt with a destructor
@@ -1678,7 +1695,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             }
         }
         let mut visitor = FakeReadCauseFinder { place, cause: None };
-        visitor.visit_body(&self.body);
+        visitor.visit_body(self.body);
         match visitor.cause {
             Some(FakeReadCause::ForMatchGuard) => Some("match guard"),
             Some(FakeReadCause::ForIndex) => Some("indexing expression"),
@@ -1736,7 +1753,8 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             // Next, look through the rest of the block, checking if we are assigning the
             // `target` (that is, the place that contains our borrow) to anything.
             let mut annotated_closure = None;
-            for stmt in &self.body[location.block].statements[location.statement_index + 1..] {
+            for stmt in &self.body[location.block].statements[location.statement_index + 1..]
+            {
                 debug!(
                     "annotate_argument_and_return_for_borrow: target={:?} stmt={:?}",
                     target, stmt
diff --git a/src/librustc_mir/borrow_check/error_reporting.rs b/src/librustc_mir/borrow_check/error_reporting.rs
index a555e0b74c2..cc15d236b23 100644
--- a/src/librustc_mir/borrow_check/error_reporting.rs
+++ b/src/librustc_mir/borrow_check/error_reporting.rs
@@ -369,8 +369,11 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                     }, field)
                 }
                 ProjectionElem::Downcast(_, variant_index) => {
-                    let base_ty =
-                        Place::ty_from(place.base, place.projection, self.body, self.infcx.tcx).ty;
+                    let base_ty = Place::ty_from(
+                        place.base,
+                        place.projection,
+                        &*self.body,
+                        self.infcx.tcx).ty;
                     self.describe_field_from_ty(&base_ty, field, Some(*variant_index))
                 }
                 ProjectionElem::Field(_, field_type) => {
@@ -498,9 +501,10 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                         },
                         ..
                     }) = bbd.terminator {
-                        if let Some(source)
-                            = BorrowedContentSource::from_call(func.ty(self.body, tcx), tcx)
-                        {
+                        if let Some(source) = BorrowedContentSource::from_call(
+                            func.ty(&*self.body, tcx),
+                            tcx
+                        ) {
                             return source;
                         }
                     }
@@ -512,7 +516,12 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
 
         // If we didn't find an overloaded deref or index, then assume it's a
         // built in deref and check the type of the base.
-        let base_ty = Place::ty_from(deref_base.base, deref_base.projection, self.body, tcx).ty;
+        let base_ty = Place::ty_from(
+            deref_base.base,
+            deref_base.projection,
+            &*self.body,
+            tcx
+        ).ty;
         if base_ty.is_unsafe_ptr() {
             BorrowedContentSource::DerefRawPointer
         } else if base_ty.is_mutable_ptr() {
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index 3a783f674e9..da08de7690a 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -9,8 +9,8 @@ use rustc::lint::builtin::UNUSED_MUT;
 use rustc::lint::builtin::{MUTABLE_BORROW_RESERVATION_CONFLICT};
 use rustc::mir::{AggregateKind, BasicBlock, BorrowCheckResult, BorrowKind};
 use rustc::mir::{
-    ClearCrossCrate, Local, Location, Body, Mutability, Operand, Place, PlaceBase, PlaceElem,
-    PlaceRef, Static, StaticKind
+    ClearCrossCrate, Local, Location, Body, BodyCache, Mutability, Operand, Place, PlaceBase,
+    PlaceElem, PlaceRef, ReadOnlyBodyCache, Static, StaticKind, read_only
 };
 use rustc::mir::{Field, ProjectionElem, Promoted, Rvalue, Statement, StatementKind};
 use rustc::mir::{Terminator, TerminatorKind};
@@ -102,7 +102,7 @@ fn mir_borrowck(tcx: TyCtxt<'_>, def_id: DefId) -> BorrowCheckResult<'_> {
 fn do_mir_borrowck<'a, 'tcx>(
     infcx: &InferCtxt<'a, 'tcx>,
     input_body: &Body<'tcx>,
-    input_promoted: &IndexVec<Promoted, Body<'tcx>>,
+    input_promoted: &IndexVec<Promoted, BodyCache<'tcx>>,
     def_id: DefId,
 ) -> BorrowCheckResult<'tcx> {
     debug!("do_mir_borrowck(def_id = {:?})", def_id);
@@ -162,16 +162,22 @@ fn do_mir_borrowck<'a, 'tcx>(
     // requires first making our own copy of the MIR. This copy will
     // be modified (in place) to contain non-lexical lifetimes. It
     // will have a lifetime tied to the inference context.
-    let mut body: Body<'tcx> = input_body.clone();
-    let mut promoted: IndexVec<Promoted, Body<'tcx>> = input_promoted.clone();
+    let body_clone: Body<'tcx> = input_body.clone();
+    let mut promoted = input_promoted.clone();
+    let mut body = BodyCache::new(body_clone);
     let free_regions =
         nll::replace_regions_in_mir(infcx, def_id, param_env, &mut body, &mut promoted);
-    let body = &body; // no further changes
-    let location_table = &LocationTable::new(body);
+    let body = read_only!(body); // no further changes
+    let promoted: IndexVec<_, _> = promoted
+        .iter_mut()
+        .map(|body| read_only!(body))
+        .collect();
+
+    let location_table = &LocationTable::new(&body);
 
     let mut errors_buffer = Vec::new();
     let (move_data, move_errors): (MoveData<'tcx>, Option<Vec<(Place<'tcx>, MoveError<'tcx>)>>) =
-        match MoveData::gather_moves(body, tcx) {
+        match MoveData::gather_moves(&body, tcx) {
             Ok(move_data) => (move_data, None),
             Err((move_data, move_errors)) => (move_data, Some(move_errors)),
         };
@@ -184,17 +190,17 @@ fn do_mir_borrowck<'a, 'tcx>(
     let dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
     let mut flow_inits = FlowAtLocation::new(do_dataflow(
         tcx,
-        body,
+        &body,
         def_id,
         &attributes,
         &dead_unwinds,
-        MaybeInitializedPlaces::new(tcx, body, &mdpe),
+        MaybeInitializedPlaces::new(tcx, &body, &mdpe),
         |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
     ));
 
     let locals_are_invalidated_at_exit = tcx.hir().body_owner_kind(id).is_fn_or_closure();
     let borrow_set = Rc::new(BorrowSet::build(
-            tcx, body, locals_are_invalidated_at_exit, &mdpe.move_data));
+        tcx, body, locals_are_invalidated_at_exit, &mdpe.move_data));
 
     // If we are in non-lexical mode, compute the non-lexical lifetimes.
     let (regioncx, polonius_output, opt_closure_req) = nll::compute_regions(
@@ -222,29 +228,29 @@ fn do_mir_borrowck<'a, 'tcx>(
 
     let flow_borrows = FlowAtLocation::new(do_dataflow(
         tcx,
-        body,
+        &body,
         def_id,
         &attributes,
         &dead_unwinds,
-        Borrows::new(tcx, body, param_env, regioncx.clone(), &borrow_set),
+        Borrows::new(tcx, &body, param_env, regioncx.clone(), &borrow_set),
         |rs, i| DebugFormatted::new(&rs.location(i)),
     ));
     let flow_uninits = FlowAtLocation::new(do_dataflow(
         tcx,
-        body,
+        &body,
         def_id,
         &attributes,
         &dead_unwinds,
-        MaybeUninitializedPlaces::new(tcx, body, &mdpe),
+        MaybeUninitializedPlaces::new(tcx, &body, &mdpe),
         |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
     ));
     let flow_ever_inits = FlowAtLocation::new(do_dataflow(
         tcx,
-        body,
+        &body,
         def_id,
         &attributes,
         &dead_unwinds,
-        EverInitializedPlaces::new(tcx, body, &mdpe),
+        EverInitializedPlaces::new(tcx, &body, &mdpe),
         |bd, i| DebugFormatted::new(&bd.move_data().inits[i]),
     ));
 
@@ -336,7 +342,8 @@ fn do_mir_borrowck<'a, 'tcx>(
 
     debug!("mbcx.used_mut: {:?}", mbcx.used_mut);
     let used_mut = mbcx.used_mut;
-    for local in mbcx.body.mut_vars_and_args_iter().filter(|local| !used_mut.contains(local)) {
+    for local in mbcx.body.mut_vars_and_args_iter().filter(|local| !used_mut.contains(local))
+    {
         let local_decl = &mbcx.body.local_decls[local];
         let lint_root = match &mbcx.body.source_scopes[local_decl.source_info.scope].local_data {
             ClearCrossCrate::Set(data) => data.lint_root,
@@ -398,7 +405,7 @@ fn do_mir_borrowck<'a, 'tcx>(
 
 crate struct MirBorrowckCtxt<'cx, 'tcx> {
     crate infcx: &'cx InferCtxt<'cx, 'tcx>,
-    body: &'cx Body<'tcx>,
+    body: ReadOnlyBodyCache<'cx, 'tcx>,
     mir_def_id: DefId,
     param_env: ty::ParamEnv<'tcx>,
     move_data: &'cx MoveData<'tcx>,
@@ -489,7 +496,7 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx
     type FlowState = Flows<'cx, 'tcx>;
 
     fn body(&self) -> &'cx Body<'tcx> {
-        self.body
+        self.body.body()
     }
 
     fn visit_block_entry(&mut self, bb: BasicBlock, flow_state: &Self::FlowState) {
@@ -639,7 +646,7 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx
                 let tcx = self.infcx.tcx;
 
                 // Compute the type with accurate region information.
-                let drop_place_ty = drop_place.ty(self.body, self.infcx.tcx);
+                let drop_place_ty = drop_place.ty(&*self.body, self.infcx.tcx);
 
                 // Erase the regions.
                 let drop_place_ty = self.infcx.tcx.erase_regions(&drop_place_ty).ty;
@@ -984,6 +991,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         let mut error_reported = false;
         let tcx = self.infcx.tcx;
         let body = self.body;
+        let body: &Body<'_> = &body;
         let param_env = self.param_env;
         let location_table = self.location_table.start_index(location);
         let borrow_set = self.borrow_set.clone();
@@ -1334,7 +1342,8 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                             _ => bug!("temporary initialized in arguments"),
                         };
 
-                        let bbd = &self.body[loc.block];
+                        let body = self.body;
+                        let bbd = &body[loc.block];
                         let stmt = &bbd.statements[loc.statement_index];
                         debug!("temporary assigned in: stmt={:?}", stmt);
 
@@ -1453,7 +1462,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         if places_conflict::borrow_conflicts_with_place(
             self.infcx.tcx,
             self.param_env,
-            self.body,
+            &self.body,
             place,
             borrow.kind,
             root_place,
@@ -1744,7 +1753,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                     // assigning to `P.f` requires `P` itself
                     // be already initialized
                     let tcx = self.infcx.tcx;
-                    let base_ty = Place::ty_from(&place.base, proj_base, self.body, tcx).ty;
+                    let base_ty = Place::ty_from(&place.base, proj_base, self.body(), tcx).ty;
                     match base_ty.kind {
                         ty::Adt(def, _) if def.has_dtor(tcx) => {
                             self.check_if_path_or_subpath_is_moved(
@@ -1851,7 +1860,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 // of the union - we should error in that case.
                 let tcx = this.infcx.tcx;
                 if let ty::Adt(def, _) =
-                    Place::ty_from(base.base, base.projection, this.body, tcx).ty.kind
+                    Place::ty_from(base.base, base.projection, this.body(), tcx).ty.kind
                 {
                     if def.is_union() {
                         if this.move_data.path_map[mpi].iter().any(|moi| {
@@ -2121,7 +2130,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 match elem {
                     ProjectionElem::Deref => {
                         let base_ty =
-                            Place::ty_from(place.base, proj_base, self.body, self.infcx.tcx).ty;
+                            Place::ty_from(place.base, proj_base, self.body(), self.infcx.tcx).ty;
 
                         // Check the kind of deref to decide
                         match base_ty.kind {
@@ -2261,7 +2270,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         match place_projection {
             [base @ .., ProjectionElem::Field(field, _ty)] => {
                 let tcx = self.infcx.tcx;
-                let base_ty = Place::ty_from(place_ref.base, base, self.body, tcx).ty;
+                let base_ty = Place::ty_from(place_ref.base, base, self.body(), tcx).ty;
 
                 if (base_ty.is_closure() || base_ty.is_generator()) &&
                     (!by_ref || self.upvars[field.index()].by_ref) {
diff --git a/src/librustc_mir/borrow_check/move_errors.rs b/src/librustc_mir/borrow_check/move_errors.rs
index bf61eb9f0c5..388a8abd5fc 100644
--- a/src/librustc_mir/borrow_check/move_errors.rs
+++ b/src/librustc_mir/borrow_check/move_errors.rs
@@ -300,7 +300,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
         // Inspect the type of the content behind the
         // borrow to provide feedback about why this
         // was a move rather than a copy.
-        let ty = deref_target_place.ty(self.body, self.infcx.tcx).ty;
+        let ty = deref_target_place.ty(&*self.body, self.infcx.tcx).ty;
         let upvar_field = self.prefixes(move_place.as_ref(), PrefixSet::All)
             .find_map(|p| self.is_upvar_field_projection(p));
 
@@ -411,7 +411,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
         };
         let move_ty = format!(
             "{:?}",
-            move_place.ty(self.body, self.infcx.tcx).ty,
+            move_place.ty(&*self.body, self.infcx.tcx).ty,
         );
         if let Ok(snippet) = self.infcx.tcx.sess.source_map().span_to_snippet(span) {
             let is_option = move_ty.starts_with("std::option::Option");
@@ -454,7 +454,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
                 }
 
                 if binds_to.is_empty() {
-                    let place_ty = move_from.ty(self.body, self.infcx.tcx).ty;
+                    let place_ty = move_from.ty(&*self.body, self.infcx.tcx).ty;
                     let place_desc = match self.describe_place(move_from.as_ref()) {
                         Some(desc) => format!("`{}`", desc),
                         None => format!("value"),
@@ -482,7 +482,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
             // No binding. Nothing to suggest.
             GroupedMoveError::OtherIllegalMove { ref original_path, use_spans, .. } => {
                 let span = use_spans.var_or_use();
-                let place_ty = original_path.ty(self.body, self.infcx.tcx).ty;
+                let place_ty = original_path.ty(&*self.body, self.infcx.tcx).ty;
                 let place_desc = match self.describe_place(original_path.as_ref()) {
                     Some(desc) => format!("`{}`", desc),
                     None => format!("value"),
diff --git a/src/librustc_mir/borrow_check/mutability_errors.rs b/src/librustc_mir/borrow_check/mutability_errors.rs
index bf070c3f07d..e135f8d1be9 100644
--- a/src/librustc_mir/borrow_check/mutability_errors.rs
+++ b/src/librustc_mir/borrow_check/mutability_errors.rs
@@ -1,6 +1,6 @@
 use rustc::hir;
 use rustc::hir::Node;
-use rustc::mir::{self, Body, ClearCrossCrate, Local, LocalInfo, Location};
+use rustc::mir::{self, ClearCrossCrate, Local, LocalInfo, Location, ReadOnlyBodyCache};
 use rustc::mir::{Mutability, Place, PlaceRef, PlaceBase, ProjectionElem};
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc_index::vec::Idx;
@@ -61,8 +61,12 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
                 projection: [proj_base @ .., ProjectionElem::Field(upvar_index, _)],
             } => {
                 debug_assert!(is_closure_or_generator(
-                    Place::ty_from(&the_place_err.base, proj_base, self.body, self.infcx.tcx).ty
-                ));
+                    Place::ty_from(
+                        &the_place_err.base,
+                        proj_base,
+                        &*self.body,
+                        self.infcx.tcx
+                    ).ty));
 
                 item_msg = format!("`{}`", access_place_desc.unwrap());
                 if self.is_upvar_field_projection(access_place.as_ref()).is_some() {
@@ -111,7 +115,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
                         Place::ty_from(
                             the_place_err.base,
                             the_place_err.projection,
-                            self.body,
+                            &*self.body,
                             self.infcx.tcx
                         )
                         .ty
@@ -225,7 +229,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
 
                 if let Some((span, message)) = annotate_struct_field(
                     self.infcx.tcx,
-                    Place::ty_from(base, proj_base, self.body, self.infcx.tcx).ty,
+                    Place::ty_from(base, proj_base, &*self.body, self.infcx.tcx).ty,
                     field,
                 ) {
                     err.span_suggestion(
@@ -300,7 +304,7 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, 'tcx> {
                 projection: [proj_base @ .., ProjectionElem::Field(upvar_index, _)],
             } => {
                 debug_assert!(is_closure_or_generator(
-                    Place::ty_from(base, proj_base, self.body, self.infcx.tcx).ty
+                    Place::ty_from(base, proj_base, &*self.body, self.infcx.tcx).ty
                 ));
 
                 err.span_label(span, format!("cannot {ACT}", ACT = act));
@@ -529,7 +533,7 @@ fn suggest_ampmut_self<'tcx>(
 // by trying (3.), then (2.) and finally falling back on (1.).
 fn suggest_ampmut<'tcx>(
     tcx: TyCtxt<'tcx>,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     local: Local,
     local_decl: &mir::LocalDecl<'tcx>,
     opt_ty_info: Option<Span>,
diff --git a/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs b/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs
index c7058531958..43aabac00bc 100644
--- a/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs
@@ -237,7 +237,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         );
 
         let regioncx = &self.nonlexical_regioncx;
-        let body = self.body;
+        let body: &Body<'_> = &self.body;
         let tcx = self.infcx.tcx;
 
         let borrow_region_vid = borrow.region;
@@ -297,9 +297,9 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 if let Some(region) = regioncx.to_error_region_vid(borrow_region_vid) {
                     let (category, from_closure, span, region_name) =
                         self.nonlexical_regioncx.free_region_constraint_info(
-                            self.body,
-                        &self.local_names,
-                        &self.upvars,
+                            &self.body,
+                            &self.local_names,
+                            &self.upvars,
                             self.mir_def_id,
                             self.infcx,
                             borrow_region_vid,
diff --git a/src/librustc_mir/borrow_check/nll/invalidation.rs b/src/librustc_mir/borrow_check/nll/invalidation.rs
index 1d429e3a6de..98679f236db 100644
--- a/src/librustc_mir/borrow_check/nll/invalidation.rs
+++ b/src/librustc_mir/borrow_check/nll/invalidation.rs
@@ -11,7 +11,7 @@ use crate::borrow_check::path_utils::*;
 use crate::dataflow::indexes::BorrowIndex;
 use rustc::ty::{self, TyCtxt};
 use rustc::mir::visit::Visitor;
-use rustc::mir::{BasicBlock, Location, Body, Place, Rvalue};
+use rustc::mir::{BasicBlock, Location, Body, Place, ReadOnlyBodyCache, Rvalue};
 use rustc::mir::{Statement, StatementKind};
 use rustc::mir::TerminatorKind;
 use rustc::mir::{Operand, BorrowKind};
@@ -22,7 +22,7 @@ pub(super) fn generate_invalidates<'tcx>(
     param_env: ty::ParamEnv<'tcx>,
     all_facts: &mut Option<AllFacts>,
     location_table: &LocationTable,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     borrow_set: &BorrowSet<'tcx>,
 ) {
     if all_facts.is_none() {
@@ -38,7 +38,7 @@ pub(super) fn generate_invalidates<'tcx>(
             param_env,
             tcx,
             location_table,
-            body,
+            body: &body,
             dominators,
         };
         ig.visit_body(body);
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 4d67b72c98c..16182fe24fa 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -12,7 +12,8 @@ use crate::borrow_check::Upvar;
 use rustc::hir::def_id::DefId;
 use rustc::infer::InferCtxt;
 use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements,
-                 Local, Location, Body, LocalKind, BasicBlock, Promoted};
+                 Local, Location, Body, BodyCache, LocalKind, BasicBlock,
+                 Promoted, ReadOnlyBodyCache};
 use rustc::ty::{self, RegionKind, RegionVid};
 use rustc_index::vec::IndexVec;
 use rustc_errors::Diagnostic;
@@ -54,8 +55,8 @@ pub(in crate::borrow_check) fn replace_regions_in_mir<'cx, 'tcx>(
     infcx: &InferCtxt<'cx, 'tcx>,
     def_id: DefId,
     param_env: ty::ParamEnv<'tcx>,
-    body: &mut Body<'tcx>,
-    promoted: &mut IndexVec<Promoted, Body<'tcx>>,
+    body: &mut BodyCache<'tcx>,
+    promoted: &mut IndexVec<Promoted, BodyCache<'tcx>>,
 ) -> UniversalRegions<'tcx> {
     debug!("replace_regions_in_mir(def_id={:?})", def_id);
 
@@ -157,8 +158,8 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
     infcx: &InferCtxt<'cx, 'tcx>,
     def_id: DefId,
     universal_regions: UniversalRegions<'tcx>,
-    body: &Body<'tcx>,
-    promoted: &IndexVec<Promoted, Body<'tcx>>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
+    promoted: &IndexVec<Promoted, ReadOnlyBodyCache<'_, 'tcx>>,
     local_names: &IndexVec<Local, Option<Symbol>>,
     upvars: &[Upvar],
     location_table: &LocationTable,
@@ -180,7 +181,8 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
 
     let universal_regions = Rc::new(universal_regions);
 
-    let elements = &Rc::new(RegionValueElements::new(body));
+    let elements
+        = &Rc::new(RegionValueElements::new(&body));
 
     // Run the MIR type-checker.
     let MirTypeckResults {
@@ -205,7 +207,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
         all_facts
             .universal_region
             .extend(universal_regions.universal_regions());
-        populate_polonius_move_facts(all_facts, move_data, location_table, body);
+        populate_polonius_move_facts(all_facts, move_data, location_table, &body);
     }
 
     // Create the region inference context, taking ownership of the
@@ -238,7 +240,6 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
         universal_regions,
         placeholder_indices,
         universal_region_relations,
-        body,
         outlives_constraints,
         member_constraints,
         closure_bounds_mapping,
@@ -253,7 +254,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
         param_env,
         &mut all_facts,
         location_table,
-        &body,
+        body,
         borrow_set,
     );
 
@@ -283,7 +284,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
 
     // Solve the region constraints.
     let closure_region_requirements =
-        regioncx.solve(infcx, body, local_names, upvars, def_id, errors_buffer);
+        regioncx.solve(infcx, &body, local_names, upvars, def_id, errors_buffer);
 
     // Dump MIR results into a file, if that is enabled. This let us
     // write unit-tests, as well as helping with debugging.
@@ -297,7 +298,13 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
 
     // We also have a `#[rustc_nll]` annotation that causes us to dump
     // information
-    dump_annotation(infcx, &body, def_id, &regioncx, &closure_region_requirements, errors_buffer);
+    dump_annotation(
+        infcx,
+        &body,
+        def_id,
+        &regioncx,
+        &closure_region_requirements,
+        errors_buffer);
 
     (regioncx, polonius_output, closure_region_requirements)
 }
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
index d44e85fa790..bd9e97e5b63 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -239,7 +239,6 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         universal_regions: Rc<UniversalRegions<'tcx>>,
         placeholder_indices: Rc<PlaceholderIndices>,
         universal_region_relations: Rc<UniversalRegionRelations<'tcx>>,
-        _body: &Body<'tcx>,
         outlives_constraints: OutlivesConstraintSet,
         member_constraints_in: MemberConstraintSet<'tcx, RegionVid>,
         closure_bounds_mapping: FxHashMap<
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/values.rs b/src/librustc_mir/borrow_check/nll/region_infer/values.rs
index 7a86536573d..b4414c514c5 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs
@@ -1,4 +1,4 @@
-use rustc::mir::{BasicBlock, Location, Body};
+use rustc::mir::{BasicBlock, Location, Body, ReadOnlyBodyCache};
 use rustc::ty::{self, RegionVid};
 use rustc_index::bit_set::{HybridBitSet, SparseBitMatrix};
 use rustc_data_structures::fx::FxHashMap;
@@ -92,7 +92,7 @@ impl RegionValueElements {
     /// Pushes all predecessors of `index` onto `stack`.
     crate fn push_predecessors(
         &self,
-        body: &Body<'_>,
+        body: ReadOnlyBodyCache<'_, '_>,
         index: PointIndex,
         stack: &mut Vec<PointIndex>,
     ) {
diff --git a/src/librustc_mir/borrow_check/nll/renumber.rs b/src/librustc_mir/borrow_check/nll/renumber.rs
index d949c7e01aa..db15d2c54fd 100644
--- a/src/librustc_mir/borrow_check/nll/renumber.rs
+++ b/src/librustc_mir/borrow_check/nll/renumber.rs
@@ -1,6 +1,6 @@
 use rustc::ty::subst::SubstsRef;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
-use rustc::mir::{Body, Location, PlaceElem, Promoted};
+use rustc::mir::{BodyCache, Location, PlaceElem, Promoted};
 use rustc::mir::visit::{MutVisitor, TyContext};
 use rustc::infer::{InferCtxt, NLLRegionVariableOrigin};
 use rustc_index::vec::IndexVec;
@@ -9,8 +9,8 @@ use rustc_index::vec::IndexVec;
 /// inference variables, returning the number of variables created.
 pub fn renumber_mir<'tcx>(
     infcx: &InferCtxt<'_, 'tcx>,
-    body: &mut Body<'tcx>,
-    promoted: &mut IndexVec<Promoted, Body<'tcx>>,
+    body: &mut BodyCache<'tcx>,
+    promoted: &mut IndexVec<Promoted, BodyCache<'tcx>>,
 ) {
     debug!("renumber_mir()");
     debug!("renumber_mir: body.arg_count={:?}", body.arg_count);
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs
index 7dee00b3eca..d6aa31449da 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs
@@ -1,7 +1,7 @@
 use crate::borrow_check::nll::region_infer::values::{PointIndex, RegionValueElements};
 use crate::util::liveness::{categorize, DefUse};
 use rustc::mir::visit::{PlaceContext, Visitor};
-use rustc::mir::{Body, Local, Location};
+use rustc::mir::{Local, Location, ReadOnlyBodyCache};
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_data_structures::vec_linked_list as vll;
 
@@ -60,7 +60,7 @@ impl LocalUseMap {
     crate fn build(
         live_locals: &Vec<Local>,
         elements: &RegionValueElements,
-        body: &Body<'_>,
+        body: ReadOnlyBodyCache<'_, '_>,
     ) -> Self {
         let nones = IndexVec::from_elem_n(None, body.local_decls.len());
         let mut local_use_map = LocalUseMap {
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
index a01b528833b..dfd505f6b61 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
@@ -7,7 +7,7 @@ use crate::borrow_check::nll::ToRegionVid;
 use crate::dataflow::move_paths::MoveData;
 use crate::dataflow::FlowAtLocation;
 use crate::dataflow::MaybeInitializedPlaces;
-use rustc::mir::{Body, Local};
+use rustc::mir::{Body, Local, ReadOnlyBodyCache};
 use rustc::ty::{RegionVid, TyCtxt};
 use rustc_data_structures::fx::FxHashSet;
 use std::rc::Rc;
@@ -28,7 +28,7 @@ mod trace;
 /// performed before
 pub(super) fn generate<'tcx>(
     typeck: &mut TypeChecker<'_, 'tcx>,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     elements: &Rc<RegionValueElements>,
     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
     move_data: &MoveData<'tcx>,
@@ -41,10 +41,9 @@ pub(super) fn generate<'tcx>(
         &typeck.borrowck_context.universal_regions,
         &typeck.borrowck_context.constraints.outlives_constraints,
     );
-    let live_locals = compute_live_locals(typeck.tcx(), &free_regions, body);
+    let live_locals = compute_live_locals(typeck.tcx(), &free_regions, &body);
     let facts_enabled = AllFacts::enabled(typeck.tcx());
 
-
     let polonius_drop_used = if facts_enabled {
         let mut drop_used = Vec::new();
         polonius::populate_access_facts(
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs
index 526ad7fb905..e67de6c99f0 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs
@@ -3,7 +3,7 @@ use crate::dataflow::indexes::MovePathIndex;
 use crate::dataflow::move_paths::{LookupResult, MoveData};
 use crate::util::liveness::{categorize, DefUse};
 use rustc::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
-use rustc::mir::{Body, Local, Location, Place};
+use rustc::mir::{Local, Location, Place, ReadOnlyBodyCache};
 use rustc::ty::subst::GenericArg;
 use rustc::ty::Ty;
 
@@ -97,7 +97,7 @@ fn add_var_uses_regions(typeck: &mut TypeChecker<'_, 'tcx>, local: Local, ty: Ty
 
 pub(super) fn populate_access_facts(
     typeck: &mut TypeChecker<'_, 'tcx>,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     location_table: &LocationTable,
     move_data: &MoveData<'_>,
     drop_used: &mut Vec<(Local, Location)>,
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
index eacc4d084db..229cbed64c2 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
@@ -7,7 +7,7 @@ use crate::dataflow::indexes::MovePathIndex;
 use crate::dataflow::move_paths::MoveData;
 use crate::dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces};
 use rustc::infer::canonical::QueryRegionConstraints;
-use rustc::mir::{BasicBlock, Body, ConstraintCategory, Local, Location};
+use rustc::mir::{BasicBlock, ConstraintCategory, Local, Location, ReadOnlyBodyCache};
 use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
 use rustc::traits::query::type_op::outlives::DropckOutlives;
 use rustc::traits::query::type_op::TypeOp;
@@ -32,7 +32,7 @@ use std::rc::Rc;
 /// this respects `#[may_dangle]` annotations).
 pub(super) fn trace(
     typeck: &mut TypeChecker<'_, 'tcx>,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     elements: &Rc<RegionValueElements>,
     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
     move_data: &MoveData<'tcx>,
@@ -71,7 +71,7 @@ struct LivenessContext<'me, 'typeck, 'flow, 'tcx> {
     elements: &'me RegionValueElements,
 
     /// MIR we are analyzing.
-    body: &'me Body<'tcx>,
+    body: ReadOnlyBodyCache<'me, 'tcx>,
 
     /// Mapping to/from the various indices used for initialization tracking.
     move_data: &'me MoveData<'tcx>,
@@ -302,7 +302,8 @@ impl LivenessResults<'me, 'typeck, 'flow, 'tcx> {
             }
         }
 
-        for &pred_block in self.cx.body.predecessors_for(block).iter() {
+        let body = self.cx.body;
+        for &pred_block in body.predecessors_for(block).iter() {
             debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,);
 
             // Check whether the variable is (at least partially)
diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
index 99bcfa9bc25..a554867389e 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -1,57 +1,59 @@
 //! This pass type-checks the MIR to ensure it is not broken.
 
-use crate::borrow_check::borrow_set::BorrowSet;
-use crate::borrow_check::location::LocationTable;
-use crate::borrow_check::nll::constraints::{OutlivesConstraintSet, OutlivesConstraint};
-use crate::borrow_check::nll::member_constraints::MemberConstraintSet;
-use crate::borrow_check::nll::facts::AllFacts;
-use crate::borrow_check::nll::region_infer::values::LivenessValues;
-use crate::borrow_check::nll::region_infer::values::PlaceholderIndex;
-use crate::borrow_check::nll::region_infer::values::PlaceholderIndices;
-use crate::borrow_check::nll::region_infer::values::RegionValueElements;
-use crate::borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest};
-use crate::borrow_check::nll::renumber;
-use crate::borrow_check::nll::type_check::free_region_relations::{
-    CreateResult, UniversalRegionRelations,
-};
-use crate::borrow_check::nll::universal_regions::{DefiningTy, UniversalRegions};
-use crate::borrow_check::nll::ToRegionVid;
-use crate::transform::promote_consts::should_suggest_const_in_array_repeat_expressions_attribute;
-use crate::dataflow::move_paths::MoveData;
-use crate::dataflow::FlowAtLocation;
-use crate::dataflow::MaybeInitializedPlaces;
+use std::{fmt, iter, mem};
+use std::rc::Rc;
+
 use either::Either;
+
 use rustc::hir;
 use rustc::hir::def_id::DefId;
+use rustc::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime, NLLRegionVariableOrigin};
 use rustc::infer::canonical::QueryRegionConstraints;
 use rustc::infer::outlives::env::RegionBoundPairs;
-use rustc::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime, NLLRegionVariableOrigin};
 use rustc::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
+use rustc::mir::*;
 use rustc::mir::interpret::PanicInfo;
 use rustc::mir::tcx::PlaceTy;
-use rustc::mir::visit::{PlaceContext, Visitor, NonMutatingUseContext};
-use rustc::mir::*;
+use rustc::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor};
+use rustc::traits::{self, ObligationCause, PredicateObligations};
+use rustc::traits::query::{Fallible, NoSolution};
 use rustc::traits::query::type_op;
 use rustc::traits::query::type_op::custom::CustomTypeOp;
-use rustc::traits::query::{Fallible, NoSolution};
-use rustc::traits::{self, ObligationCause, PredicateObligations};
-use rustc::ty::adjustment::{PointerCast};
-use rustc::ty::cast::CastTy;
-use rustc::ty::fold::TypeFoldable;
-use rustc::ty::subst::{Subst, SubstsRef, GenericArgKind, UserSubsts};
 use rustc::ty::{
-    self, RegionVid, ToPolyTraitRef, Ty, TyCtxt, UserType,
-    CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
+    self, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, RegionVid, ToPolyTraitRef, Ty,
+    TyCtxt, UserType,
     UserTypeAnnotationIndex,
 };
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
-use rustc_index::vec::{IndexVec, Idx};
+use rustc::ty::adjustment::PointerCast;
+use rustc::ty::cast::CastTy;
+use rustc::ty::fold::TypeFoldable;
 use rustc::ty::layout::VariantIdx;
-use std::rc::Rc;
-use std::{fmt, iter, mem};
-use syntax_pos::{Span, DUMMY_SP};
-
+use rustc::ty::subst::{GenericArgKind, Subst, SubstsRef, UserSubsts};
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_error_codes::*;
+use rustc_index::vec::{Idx, IndexVec};
+use syntax_pos::{DUMMY_SP, Span};
+
+use crate::borrow_check::borrow_set::BorrowSet;
+use crate::borrow_check::location::LocationTable;
+use crate::borrow_check::nll::constraints::{OutlivesConstraint, OutlivesConstraintSet};
+use crate::borrow_check::nll::facts::AllFacts;
+use crate::borrow_check::nll::member_constraints::MemberConstraintSet;
+use crate::borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest};
+use crate::borrow_check::nll::region_infer::values::LivenessValues;
+use crate::borrow_check::nll::region_infer::values::PlaceholderIndex;
+use crate::borrow_check::nll::region_infer::values::PlaceholderIndices;
+use crate::borrow_check::nll::region_infer::values::RegionValueElements;
+use crate::borrow_check::nll::renumber;
+use crate::borrow_check::nll::ToRegionVid;
+use crate::borrow_check::nll::type_check::free_region_relations::{
+    CreateResult, UniversalRegionRelations,
+};
+use crate::borrow_check::nll::universal_regions::{DefiningTy, UniversalRegions};
+use crate::dataflow::FlowAtLocation;
+use crate::dataflow::MaybeInitializedPlaces;
+use crate::dataflow::move_paths::MoveData;
+use crate::transform::promote_consts::should_suggest_const_in_array_repeat_expressions_attribute;
 
 macro_rules! span_mirbug {
     ($context:expr, $elem:expr, $($message:tt)*) => ({
@@ -115,8 +117,8 @@ mod relate_tys;
 pub(crate) fn type_check<'tcx>(
     infcx: &InferCtxt<'_, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
-    body: &Body<'tcx>,
-    promoted: &IndexVec<Promoted, Body<'tcx>>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
+    promoted: &IndexVec<Promoted, ReadOnlyBodyCache<'_, 'tcx>>,
     mir_def_id: DefId,
     universal_regions: &Rc<UniversalRegions<'tcx>>,
     location_table: &LocationTable,
@@ -168,8 +170,17 @@ pub(crate) fn type_check<'tcx>(
         &mut borrowck_context,
         &universal_region_relations,
         |mut cx| {
-            cx.equate_inputs_and_outputs(body, universal_regions, &normalized_inputs_and_output);
-            liveness::generate(&mut cx, body, elements, flow_inits, move_data, location_table);
+            cx.equate_inputs_and_outputs(
+                &body,
+                universal_regions,
+                &normalized_inputs_and_output);
+            liveness::generate(
+                &mut cx,
+                body,
+                elements,
+                flow_inits,
+                move_data,
+                location_table);
 
             translate_outlives_facts(cx.borrowck_context);
         },
@@ -185,17 +196,17 @@ fn type_check_internal<'a, 'tcx, R>(
     infcx: &'a InferCtxt<'a, 'tcx>,
     mir_def_id: DefId,
     param_env: ty::ParamEnv<'tcx>,
-    body: &'a Body<'tcx>,
-    promoted: &'a IndexVec<Promoted, Body<'tcx>>,
+    body: ReadOnlyBodyCache<'a, 'tcx>,
+    promoted: &'a IndexVec<Promoted, ReadOnlyBodyCache<'_, 'tcx>>,
     region_bound_pairs: &'a RegionBoundPairs<'tcx>,
     implicit_region_bound: ty::Region<'tcx>,
     borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>,
     universal_region_relations: &'a UniversalRegionRelations<'tcx>,
     mut extra: impl FnMut(&mut TypeChecker<'a, 'tcx>) -> R,
-) -> R where {
+) -> R {
     let mut checker = TypeChecker::new(
         infcx,
-        body,
+        body.body(),
         mir_def_id,
         param_env,
         region_bound_pairs,
@@ -204,7 +215,7 @@ fn type_check_internal<'a, 'tcx, R>(
         universal_region_relations,
     );
     let errors_reported = {
-        let mut verifier = TypeVerifier::new(&mut checker, body, promoted);
+        let mut verifier = TypeVerifier::new(&mut checker, body.body(), promoted);
         verifier.visit_body(body);
         verifier.errors_reported
     };
@@ -261,7 +272,7 @@ enum FieldAccessError {
 struct TypeVerifier<'a, 'b, 'tcx> {
     cx: &'a mut TypeChecker<'b, 'tcx>,
     body: &'b Body<'tcx>,
-    promoted: &'b IndexVec<Promoted, Body<'tcx>>,
+    promoted: &'b IndexVec<Promoted, ReadOnlyBodyCache<'b, 'tcx>>,
     last_span: Span,
     mir_def_id: DefId,
     errors_reported: bool,
@@ -385,7 +396,7 @@ impl<'a, 'b, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'tcx> {
         }
     }
 
-    fn visit_body(&mut self, body: &Body<'tcx>) {
+    fn visit_body(&mut self, body: ReadOnlyBodyCache<'_, 'tcx>) {
         self.sanitize_type(&"return type", body.return_ty());
         for local_decl in &body.local_decls {
             self.sanitize_type(local_decl, local_decl.ty);
@@ -401,7 +412,7 @@ impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> {
     fn new(
         cx: &'a mut TypeChecker<'b, 'tcx>,
         body: &'b Body<'tcx>,
-        promoted: &'b IndexVec<Promoted, Body<'tcx>>,
+        promoted: &'b IndexVec<Promoted, ReadOnlyBodyCache<'b, 'tcx>>,
     ) -> Self {
         TypeVerifier {
             body,
@@ -464,10 +475,10 @@ impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> {
                 match kind {
                     StaticKind::Promoted(promoted, _) => {
                         if !self.errors_reported {
-                            let promoted_body = &self.promoted[*promoted];
-                            self.sanitize_promoted(promoted_body, location);
+                            let promoted_body_cache = self.promoted[*promoted];
+                            self.sanitize_promoted(promoted_body_cache, location);
 
-                            let promoted_ty = promoted_body.return_ty();
+                            let promoted_ty = promoted_body_cache.return_ty();
                             check_err(self, place, promoted_ty, san_ty);
                         }
                     }
@@ -535,12 +546,16 @@ impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> {
         place_ty
     }
 
-    fn sanitize_promoted(&mut self, promoted_body: &'b Body<'tcx>, location: Location) {
+    fn sanitize_promoted(
+        &mut self,
+        promoted_body: ReadOnlyBodyCache<'b, 'tcx>,
+        location: Location
+    ) {
         // Determine the constraints from the promoted MIR by running the type
         // checker on the promoted MIR, then transfer the constraints back to
         // the main MIR, changing the locations to the provided location.
 
-        let parent_body = mem::replace(&mut self.body, promoted_body);
+        let parent_body = mem::replace(&mut self.body, promoted_body.body());
 
         // Use new sets of constraints and closure bounds so that we can
         // modify their locations.
@@ -548,7 +563,7 @@ impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> {
         let mut constraints = Default::default();
         let mut closure_bounds = Default::default();
         let mut liveness_constraints = LivenessValues::new(
-            Rc::new(RegionValueElements::new(promoted_body)),
+            Rc::new(RegionValueElements::new(&promoted_body)),
         );
         // Don't try to add borrow_region facts for the promoted MIR
 
@@ -1361,7 +1376,12 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         self.infcx.tcx
     }
 
-    fn check_stmt(&mut self, body: &Body<'tcx>, stmt: &Statement<'tcx>, location: Location) {
+    fn check_stmt(
+        &mut self,
+        body: ReadOnlyBodyCache<'_, 'tcx>,
+        stmt: &Statement<'tcx>,
+        location: Location)
+    {
         debug!("check_stmt: {:?}", stmt);
         let tcx = self.tcx();
         match stmt.kind {
@@ -1393,9 +1413,9 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     _ => ConstraintCategory::Assignment,
                 };
 
-                let place_ty = place.ty(body, tcx).ty;
+                let place_ty = place.ty(&*body, tcx).ty;
                 let place_ty = self.normalize(place_ty, location);
-                let rv_ty = rv.ty(body, tcx);
+                let rv_ty = rv.ty(&*body, tcx);
                 let rv_ty = self.normalize(rv_ty, location);
                 if let Err(terr) =
                     self.sub_types_or_anon(rv_ty, place_ty, location.to_locations(), category)
@@ -1447,7 +1467,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                 ref place,
                 variant_index,
             } => {
-                let place_type = place.ty(body, tcx).ty;
+                let place_type = place.ty(&*body, tcx).ty;
                 let adt = match place_type.kind {
                     ty::Adt(adt, _) if adt.is_enum() => adt,
                     _ => {
@@ -1469,7 +1489,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                 };
             }
             StatementKind::AscribeUserType(box(ref place, ref projection), variance) => {
-                let place_ty = place.ty(body, tcx).ty;
+                let place_ty = place.ty(&*body, tcx).ty;
                 if let Err(terr) = self.relate_type_and_user_type(
                     place_ty,
                     variance,
@@ -1972,12 +1992,17 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         }
     }
 
-    fn check_rvalue(&mut self, body: &Body<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) {
+    fn check_rvalue(
+        &mut self,
+        body: ReadOnlyBodyCache<'_, 'tcx>,
+        rvalue: &Rvalue<'tcx>,
+        location: Location)
+    {
         let tcx = self.tcx();
 
         match rvalue {
             Rvalue::Aggregate(ak, ops) => {
-                self.check_aggregate_rvalue(body, rvalue, ak, ops, location)
+                self.check_aggregate_rvalue(&body, rvalue, ak, ops, location)
             }
 
             Rvalue::Repeat(operand, len) => if *len > 1 {
@@ -1985,7 +2010,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     // While this is located in `nll::typeck` this error is not an NLL error, it's
                     // a required check to make sure that repeated elements implement `Copy`.
                     let span = body.source_info(location).span;
-                    let ty = operand.ty(body, tcx);
+                    let ty = operand.ty(&*body, tcx);
                     if !self.infcx.type_is_copy_modulo_regions(self.param_env, ty, span) {
                         // To determine if `const_in_array_repeat_expressions` feature gate should
                         // be mentioned, need to check if the rvalue is promotable.
@@ -2039,7 +2064,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
             Rvalue::Cast(cast_kind, op, ty) => {
                 match cast_kind {
                     CastKind::Pointer(PointerCast::ReifyFnPointer) => {
-                        let fn_sig = op.ty(body, tcx).fn_sig(tcx);
+                        let fn_sig = op.ty(&*body, tcx).fn_sig(tcx);
 
                         // The type that we see in the fcx is like
                         // `foo::<'a, 'b>`, where `foo` is the path to a
@@ -2068,7 +2093,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     }
 
                     CastKind::Pointer(PointerCast::ClosureFnPointer(unsafety)) => {
-                        let sig = match op.ty(body, tcx).kind {
+                        let sig = match op.ty(&*body, tcx).kind {
                             ty::Closure(def_id, substs) => {
                                 substs.as_closure().sig_ty(def_id, tcx).fn_sig(tcx)
                             }
@@ -2094,7 +2119,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     }
 
                     CastKind::Pointer(PointerCast::UnsafeFnPointer) => {
-                        let fn_sig = op.ty(body, tcx).fn_sig(tcx);
+                        let fn_sig = op.ty(&*body, tcx).fn_sig(tcx);
 
                         // The type that we see in the fcx is like
                         // `foo::<'a, 'b>`, where `foo` is the path to a
@@ -2126,7 +2151,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                         let &ty = ty;
                         let trait_ref = ty::TraitRef {
                             def_id: tcx.lang_items().coerce_unsized_trait().unwrap(),
-                            substs: tcx.mk_substs_trait(op.ty(body, tcx), &[ty.into()]),
+                            substs: tcx.mk_substs_trait(op.ty(&*body, tcx), &[ty.into()]),
                         };
 
                         self.prove_trait_ref(
@@ -2137,7 +2162,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     }
 
                     CastKind::Pointer(PointerCast::MutToConstPointer) => {
-                        let ty_from = match op.ty(body, tcx).kind {
+                        let ty_from = match op.ty(&*body, tcx).kind {
                             ty::RawPtr(ty::TypeAndMut {
                                 ty: ty_from,
                                 mutbl: hir::Mutability::Mutable,
@@ -2185,7 +2210,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     }
 
                     CastKind::Pointer(PointerCast::ArrayToPointer)  => {
-                        let ty_from = op.ty(body, tcx);
+                        let ty_from = op.ty(&*body, tcx);
 
                         let opt_ty_elem = match ty_from.kind {
                             ty::RawPtr(
@@ -2247,7 +2272,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     }
 
                     CastKind::Misc => {
-                        let ty_from = op.ty(body, tcx);
+                        let ty_from = op.ty(&*body, tcx);
                         let cast_ty_from = CastTy::from_ty(ty_from);
                         let cast_ty_to = CastTy::from_ty(ty);
                         match (cast_ty_from, cast_ty_to) {
@@ -2305,7 +2330,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
             }
 
             Rvalue::Ref(region, _borrow_kind, borrowed_place) => {
-                self.add_reborrow_constraint(body, location, region, borrowed_place);
+                self.add_reborrow_constraint(&body, location, region, borrowed_place);
             }
 
             Rvalue::BinaryOp(BinOp::Eq, left, right)
@@ -2314,9 +2339,9 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
             | Rvalue::BinaryOp(BinOp::Le, left, right)
             | Rvalue::BinaryOp(BinOp::Gt, left, right)
             | Rvalue::BinaryOp(BinOp::Ge, left, right) => {
-                let ty_left = left.ty(body, tcx);
+                let ty_left = left.ty(&*body, tcx);
                 if let ty::RawPtr(_) | ty::FnPtr(_) = ty_left.kind {
-                    let ty_right = right.ty(body, tcx);
+                    let ty_right = right.ty(&*body, tcx);
                     let common_ty = self.infcx.next_ty_var(
                         TypeVariableOrigin {
                             kind: TypeVariableOriginKind::MiscVariable,
@@ -2741,12 +2766,12 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         })
     }
 
-    fn typeck_mir(&mut self, body: &Body<'tcx>) {
+    fn typeck_mir(&mut self, body: ReadOnlyBodyCache<'_, 'tcx>) {
         self.last_span = body.span;
         debug!("run_on_mir: {:?}", body.span);
 
         for (local, local_decl) in body.local_decls.iter_enumerated() {
-            self.check_local(body, local, local_decl);
+            self.check_local(&body, local, local_decl);
         }
 
         for (block, block_data) in body.basic_blocks().iter_enumerated() {
@@ -2762,8 +2787,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                 location.statement_index += 1;
             }
 
-            self.check_terminator(body, block_data.terminator(), location);
-            self.check_iscleanup(body, block_data);
+            self.check_terminator(&body, block_data.terminator(), location);
+            self.check_iscleanup(&body, block_data);
         }
     }
 
diff --git a/src/librustc_mir/borrow_check/prefixes.rs b/src/librustc_mir/borrow_check/prefixes.rs
index 57833cac9cb..06b9d4dbde0 100644
--- a/src/librustc_mir/borrow_check/prefixes.rs
+++ b/src/librustc_mir/borrow_check/prefixes.rs
@@ -11,7 +11,7 @@ use super::MirBorrowckCtxt;
 
 use rustc::hir;
 use rustc::ty::{self, TyCtxt};
-use rustc::mir::{Body, Place, PlaceBase, PlaceRef, ProjectionElem};
+use rustc::mir::{Place, PlaceBase, PlaceRef, ProjectionElem, ReadOnlyBodyCache};
 
 pub trait IsPrefixOf<'cx, 'tcx> {
     fn is_prefix_of(&self, other: PlaceRef<'cx, 'tcx>) -> bool;
@@ -26,7 +26,7 @@ impl<'cx, 'tcx> IsPrefixOf<'cx, 'tcx> for PlaceRef<'cx, 'tcx> {
 }
 
 pub(super) struct Prefixes<'cx, 'tcx> {
-    body: &'cx Body<'tcx>,
+    body: ReadOnlyBodyCache<'cx, 'tcx>,
     tcx: TyCtxt<'tcx>,
     kind: PrefixSet,
     next: Option<PlaceRef<'cx, 'tcx>>,
@@ -143,7 +143,7 @@ impl<'cx, 'tcx> Iterator for Prefixes<'cx, 'tcx> {
                     // derefs, except we stop at the deref of a shared
                     // reference.
 
-                    let ty = Place::ty_from(cursor.base, proj_base, self.body, self.tcx).ty;
+                    let ty = Place::ty_from(cursor.base, proj_base, &*self.body, self.tcx).ty;
                     match ty.kind {
                         ty::RawPtr(_) |
                         ty::Ref(
diff --git a/src/librustc_mir/build/mod.rs b/src/librustc_mir/build/mod.rs
index eb9b401f272..b84461d6b92 100644
--- a/src/librustc_mir/build/mod.rs
+++ b/src/librustc_mir/build/mod.rs
@@ -24,7 +24,7 @@ use syntax_pos::Span;
 use super::lints;
 
 /// Construct the MIR for a given `DefId`.
-pub fn mir_build(tcx: TyCtxt<'_>, def_id: DefId) -> Body<'_> {
+pub fn mir_build(tcx: TyCtxt<'_>, def_id: DefId) -> BodyCache<'_> {
     let id = tcx.hir().as_local_hir_id(def_id).unwrap();
 
     // Figure out what primary body this item has.
@@ -196,6 +196,8 @@ pub fn mir_build(tcx: TyCtxt<'_>, def_id: DefId) -> Body<'_> {
 
         lints::check(tcx, &body, def_id);
 
+        let mut body = BodyCache::new(body);
+        body.ensure_predecessors();
         body
     })
 }
diff --git a/src/librustc_mir/const_eval.rs b/src/librustc_mir/const_eval.rs
index ff0cf6f4fdd..a3eac1eecf0 100644
--- a/src/librustc_mir/const_eval.rs
+++ b/src/librustc_mir/const_eval.rs
@@ -354,7 +354,7 @@ impl<'mir, 'tcx> interpret::Machine<'mir, 'tcx> for CompileTimeInterpreter<'mir,
         }
         // This is a const fn. Call it.
         Ok(Some(match ecx.load_mir(instance.def, None) {
-            Ok(body) => body,
+            Ok(body) => body.body(),
             Err(err) => {
                 if let err_unsup!(NoMirFor(ref path)) = err.kind {
                     return Err(
@@ -731,7 +731,7 @@ pub fn const_eval_raw_provider<'tcx>(
 
     let res = ecx.load_mir(cid.instance.def, cid.promoted);
     res.and_then(
-        |body| eval_body_using_ecx(&mut ecx, cid, body)
+        |body| eval_body_using_ecx(&mut ecx, cid, body.body())
     ).and_then(|place| {
         Ok(RawConst {
             alloc_id: place.ptr.assert_ptr().alloc_id,
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 402e5aeacbf..7e7652cdab5 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -98,7 +98,7 @@ fn precompute_borrows_out_of_scope<'tcx>(
             // Add successor BBs to the work list, if necessary.
             let bb_data = &body[bb];
             assert!(hi == bb_data.statements.len());
-            for &succ_bb in bb_data.terminator.as_ref().unwrap().successors() {
+            for &succ_bb in bb_data.terminator().successors() {
                 visited.entry(succ_bb)
                     .and_modify(|lo| {
                         // `succ_bb` has been seen before. If it wasn't
@@ -153,8 +153,8 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> {
         }
 
         Borrows {
-            tcx: tcx,
-            body: body,
+            tcx,
+            body,
             param_env,
             borrow_set: borrow_set.clone(),
             borrows_out_of_scope_at_location,
diff --git a/src/librustc_mir/dataflow/impls/mod.rs b/src/librustc_mir/dataflow/impls/mod.rs
index 6f860d00a22..0fb912b5fcb 100644
--- a/src/librustc_mir/dataflow/impls/mod.rs
+++ b/src/librustc_mir/dataflow/impls/mod.rs
@@ -71,7 +71,7 @@ pub struct MaybeInitializedPlaces<'a, 'tcx> {
 
 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
-        MaybeInitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
+        MaybeInitializedPlaces { tcx, body, mdpe }
     }
 }
 
@@ -122,7 +122,7 @@ pub struct MaybeUninitializedPlaces<'a, 'tcx> {
 
 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
-        MaybeUninitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
+        MaybeUninitializedPlaces { tcx, body, mdpe }
     }
 }
 
@@ -172,7 +172,7 @@ pub struct DefinitelyInitializedPlaces<'a, 'tcx> {
 
 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
-        DefinitelyInitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
+        DefinitelyInitializedPlaces { tcx, body, mdpe }
     }
 }
 
@@ -217,7 +217,7 @@ pub struct EverInitializedPlaces<'a, 'tcx> {
 
 impl<'a, 'tcx> EverInitializedPlaces<'a, 'tcx> {
     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
-        EverInitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
+        EverInitializedPlaces { tcx, body, mdpe }
     }
 }
 
diff --git a/src/librustc_mir/dataflow/impls/storage_liveness.rs b/src/librustc_mir/dataflow/impls/storage_liveness.rs
index 1b81032bfe6..c4b97d12e62 100644
--- a/src/librustc_mir/dataflow/impls/storage_liveness.rs
+++ b/src/librustc_mir/dataflow/impls/storage_liveness.rs
@@ -75,24 +75,26 @@ impl<'a, 'tcx> BottomValue for MaybeStorageLive<'a, 'tcx> {
 /// Dataflow analysis that determines whether each local requires storage at a
 /// given location; i.e. whether its storage can go away without being observed.
 pub struct RequiresStorage<'mir, 'tcx> {
-    body: &'mir Body<'tcx>,
+    body: ReadOnlyBodyCache<'mir, 'tcx>,
     borrowed_locals:
         RefCell<DataflowResultsRefCursor<'mir, 'tcx, HaveBeenBorrowedLocals<'mir, 'tcx>>>,
 }
 
 impl<'mir, 'tcx: 'mir> RequiresStorage<'mir, 'tcx> {
     pub fn new(
-        body: &'mir Body<'tcx>,
+        body: ReadOnlyBodyCache<'mir, 'tcx>,
         borrowed_locals: &'mir DataflowResults<'tcx, HaveBeenBorrowedLocals<'mir, 'tcx>>,
     ) -> Self {
         RequiresStorage {
             body,
-            borrowed_locals: RefCell::new(DataflowResultsCursor::new(borrowed_locals, body)),
+            borrowed_locals: RefCell::new(
+                DataflowResultsCursor::new(borrowed_locals, body.body())
+            ),
         }
     }
 
     pub fn body(&self) -> &Body<'tcx> {
-        self.body
+        &self.body
     }
 }
 
diff --git a/src/librustc_mir/interpret/eval_context.rs b/src/librustc_mir/interpret/eval_context.rs
index 8250cadb01d..9af47f3e77f 100644
--- a/src/librustc_mir/interpret/eval_context.rs
+++ b/src/librustc_mir/interpret/eval_context.rs
@@ -312,7 +312,7 @@ impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
         &self,
         instance: ty::InstanceDef<'tcx>,
         promoted: Option<mir::Promoted>,
-    ) -> InterpResult<'tcx, &'tcx mir::Body<'tcx>> {
+    ) -> InterpResult<'tcx, mir::ReadOnlyBodyCache<'tcx, 'tcx>> {
         // do not continue if typeck errors occurred (can only occur in local crate)
         let did = instance.def_id();
         if did.is_local()
@@ -323,11 +323,11 @@ impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
         }
         trace!("load mir(instance={:?}, promoted={:?})", instance, promoted);
         if let Some(promoted) = promoted {
-            return Ok(&self.tcx.promoted_mir(did)[promoted]);
+            return Ok(self.tcx.promoted_mir(did)[promoted].unwrap_read_only());
         }
         match instance {
             ty::InstanceDef::Item(def_id) => if self.tcx.is_mir_available(did) {
-                Ok(self.tcx.optimized_mir(did))
+                Ok(self.tcx.optimized_mir(did).unwrap_read_only())
             } else {
                 throw_unsup!(NoMirFor(self.tcx.def_path_str(def_id)))
             },
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index a4c4c7ff616..4fe53cf35e5 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -1255,7 +1255,7 @@ fn collect_neighbours<'tcx>(
         body: &body,
         output,
         param_substs: instance.substs,
-    }.visit_body(&body);
+    }.visit_body(body);
 }
 
 fn def_id_to_string(tcx: TyCtxt<'_>, def_id: DefId) -> String {
diff --git a/src/librustc_mir/shim.rs b/src/librustc_mir/shim.rs
index 708686fdcf9..680f75eb84e 100644
--- a/src/librustc_mir/shim.rs
+++ b/src/librustc_mir/shim.rs
@@ -26,7 +26,7 @@ pub fn provide(providers: &mut Providers<'_>) {
     providers.mir_shims = make_shim;
 }
 
-fn make_shim<'tcx>(tcx: TyCtxt<'tcx>, instance: ty::InstanceDef<'tcx>) -> &'tcx Body<'tcx> {
+fn make_shim<'tcx>(tcx: TyCtxt<'tcx>, instance: ty::InstanceDef<'tcx>) -> &'tcx BodyCache<'tcx> {
     debug!("make_shim({:?})", instance);
 
     let mut result = match instance {
@@ -125,6 +125,7 @@ fn make_shim<'tcx>(tcx: TyCtxt<'tcx>, instance: ty::InstanceDef<'tcx>) -> &'tcx
 
     debug!("make_shim({:?}) = {:?}", instance, result);
 
+    result.ensure_predecessors();
     tcx.arena.alloc(result)
 }
 
@@ -164,7 +165,9 @@ fn local_decls_for_sig<'tcx>(sig: &ty::FnSig<'tcx>, span: Span)
         .collect()
 }
 
-fn build_drop_shim<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, ty: Option<Ty<'tcx>>) -> Body<'tcx> {
+fn build_drop_shim<'tcx>(
+    tcx: TyCtxt<'tcx>, def_id: DefId, ty: Option<Ty<'tcx>>
+) -> BodyCache<'tcx> {
     debug!("build_drop_shim(def_id={:?}, ty={:?})", def_id, ty);
 
     // Check if this is a generator, if so, return the drop glue for it
@@ -196,12 +199,14 @@ fn build_drop_shim<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, ty: Option<Ty<'tcx>>)
     block(&mut blocks, TerminatorKind::Goto { target: return_block });
     block(&mut blocks, TerminatorKind::Return);
 
-    let mut body = new_body(
+    let body = new_body(
         blocks,
         local_decls_for_sig(&sig, span),
         sig.inputs().len(),
         span);
 
+    let mut body = BodyCache::new(body);
+
     if let Some(..) = ty {
         // The first argument (index 0), but add 1 for the return value.
         let dropee_ptr = Place::from(Local::new(1+0));
@@ -314,7 +319,7 @@ impl<'a, 'tcx> DropElaborator<'a, 'tcx> for DropShimElaborator<'a, 'tcx> {
 }
 
 /// Builds a `Clone::clone` shim for `self_ty`. Here, `def_id` is `Clone::clone`.
-fn build_clone_shim<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, self_ty: Ty<'tcx>) -> Body<'tcx> {
+fn build_clone_shim<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, self_ty: Ty<'tcx>) -> BodyCache<'tcx> {
     debug!("build_clone_shim(def_id={:?})", def_id);
 
     let param_env = tcx.param_env(def_id);
@@ -343,7 +348,7 @@ fn build_clone_shim<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, self_ty: Ty<'tcx>) -
         }
     };
 
-    builder.into_mir()
+    BodyCache::new(builder.into_mir())
 }
 
 struct CloneShimBuilder<'tcx> {
@@ -704,7 +709,7 @@ fn build_call_shim<'tcx>(
     rcvr_adjustment: Adjustment,
     call_kind: CallKind,
     untuple_args: Option<&[Ty<'tcx>]>,
-) -> Body<'tcx> {
+) -> BodyCache<'tcx> {
     debug!("build_call_shim(def_id={:?}, rcvr_adjustment={:?}, \
             call_kind={:?}, untuple_args={:?})",
            def_id, rcvr_adjustment, call_kind, untuple_args);
@@ -839,10 +844,10 @@ fn build_call_shim<'tcx>(
     if let Abi::RustCall = sig.abi {
         body.spread_arg = Some(Local::new(sig.inputs().len()));
     }
-    body
+    BodyCache::new(body)
 }
 
-pub fn build_adt_ctor(tcx: TyCtxt<'_>, ctor_id: DefId) -> &Body<'_> {
+pub fn build_adt_ctor(tcx: TyCtxt<'_>, ctor_id: DefId) -> &BodyCache<'_> {
     debug_assert!(tcx.is_constructor(ctor_id));
 
     let span = tcx.hir().span_if_local(ctor_id)
@@ -926,5 +931,7 @@ pub fn build_adt_ctor(tcx: TyCtxt<'_>, ctor_id: DefId) -> &Body<'_> {
         |_, _| Ok(()),
     );
 
+    let mut body = BodyCache::new(body);
+    body.ensure_predecessors();
     tcx.arena.alloc(body)
 }
diff --git a/src/librustc_mir/transform/add_call_guards.rs b/src/librustc_mir/transform/add_call_guards.rs
index bf3df1ae2fd..35238e2d08a 100644
--- a/src/librustc_mir/transform/add_call_guards.rs
+++ b/src/librustc_mir/transform/add_call_guards.rs
@@ -31,15 +31,16 @@ pub use self::AddCallGuards::*;
  */
 
 impl<'tcx> MirPass<'tcx> for AddCallGuards {
-    fn run_pass(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         self.add_call_guards(body);
     }
 }
 
 impl AddCallGuards {
-    pub fn add_call_guards(&self, body: &mut Body<'_>) {
-        let pred_count: IndexVec<_, _> =
-            body.predecessors().iter().map(|ps| ps.len()).collect();
+    pub fn add_call_guards(&self, body: &mut BodyCache<'_>) {
+        let pred_count: IndexVec<_, _> = body.predecessors().iter().map(|ps| ps.len()).collect();
 
         // We need a place to store the new blocks generated
         let mut new_blocks = Vec::new();
diff --git a/src/librustc_mir/transform/add_moves_for_packed_drops.rs b/src/librustc_mir/transform/add_moves_for_packed_drops.rs
index 052631ddff3..98c6a5ed077 100644
--- a/src/librustc_mir/transform/add_moves_for_packed_drops.rs
+++ b/src/librustc_mir/transform/add_moves_for_packed_drops.rs
@@ -40,13 +40,15 @@ use crate::util;
 pub struct AddMovesForPackedDrops;
 
 impl<'tcx> MirPass<'tcx> for AddMovesForPackedDrops {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         debug!("add_moves_for_packed_drops({:?} @ {:?})", src, body.span);
         add_moves_for_packed_drops(tcx, body, src.def_id());
     }
 }
 
-pub fn add_moves_for_packed_drops<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>, def_id: DefId) {
+pub fn add_moves_for_packed_drops<'tcx>(
+    tcx: TyCtxt<'tcx>, body: &mut BodyCache<'tcx>, def_id: DefId
+) {
     let patch = add_moves_for_packed_drops_patch(tcx, body, def_id);
     patch.apply(body);
 }
diff --git a/src/librustc_mir/transform/add_retag.rs b/src/librustc_mir/transform/add_retag.rs
index b56a1b263fd..e6ad37ae113 100644
--- a/src/librustc_mir/transform/add_retag.rs
+++ b/src/librustc_mir/transform/add_retag.rs
@@ -59,7 +59,7 @@ fn may_be_reference<'tcx>(ty: Ty<'tcx>) -> bool {
 }
 
 impl<'tcx> MirPass<'tcx> for AddRetag {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         if !tcx.sess.opts.debugging_opts.mir_emit_retag {
             return;
         }
diff --git a/src/librustc_mir/transform/check_consts/mod.rs b/src/librustc_mir/transform/check_consts/mod.rs
index 4d00aaf7abc..7095b3fa0aa 100644
--- a/src/librustc_mir/transform/check_consts/mod.rs
+++ b/src/librustc_mir/transform/check_consts/mod.rs
@@ -20,7 +20,7 @@ pub mod validation;
 /// Information about the item currently being const-checked, as well as a reference to the global
 /// context.
 pub struct Item<'mir, 'tcx> {
-    pub body: &'mir mir::Body<'tcx>,
+    pub body: mir::ReadOnlyBodyCache<'mir, 'tcx>,
     pub tcx: TyCtxt<'tcx>,
     pub def_id: DefId,
     pub param_env: ty::ParamEnv<'tcx>,
@@ -31,7 +31,7 @@ impl Item<'mir, 'tcx> {
     pub fn new(
         tcx: TyCtxt<'tcx>,
         def_id: DefId,
-        body: &'mir mir::Body<'tcx>,
+        body: mir::ReadOnlyBodyCache<'mir, 'tcx>,
     ) -> Self {
         let param_env = tcx.param_env(def_id);
         let const_kind = ConstKind::for_item(tcx, def_id);
diff --git a/src/librustc_mir/transform/check_consts/qualifs.rs b/src/librustc_mir/transform/check_consts/qualifs.rs
index 2d5a0a2afcd..62b4a4ccc98 100644
--- a/src/librustc_mir/transform/check_consts/qualifs.rs
+++ b/src/librustc_mir/transform/check_consts/qualifs.rs
@@ -51,7 +51,7 @@ pub trait Qualif {
             });
             let qualif = base_qualif && Self::in_any_value_of_ty(
                 cx,
-                Place::ty_from(place.base, proj_base, cx.body, cx.tcx)
+                Place::ty_from(place.base, proj_base, &*cx.body, cx.tcx)
                     .projection_ty(cx.tcx, elem)
                     .ty,
             );
@@ -155,7 +155,7 @@ pub trait Qualif {
                 // Special-case reborrows to be more like a copy of the reference.
                 if let &[ref proj_base @ .., elem] = place.projection.as_ref() {
                     if ProjectionElem::Deref == elem {
-                        let base_ty = Place::ty_from(&place.base, proj_base, cx.body, cx.tcx).ty;
+                        let base_ty = Place::ty_from(&place.base, proj_base, &*cx.body, cx.tcx).ty;
                         if let ty::Ref(..) = base_ty.kind {
                             return Self::in_place(cx, per_local, PlaceRef {
                                 base: &place.base,
@@ -221,7 +221,7 @@ impl Qualif for HasMutInterior {
             Rvalue::Aggregate(ref kind, _) => {
                 if let AggregateKind::Adt(def, ..) = **kind {
                     if Some(def.did) == cx.tcx.lang_items().unsafe_cell_type() {
-                        let ty = rvalue.ty(cx.body, cx.tcx);
+                        let ty = rvalue.ty(&*cx.body, cx.tcx);
                         assert_eq!(Self::in_any_value_of_ty(cx, ty), true);
                         return true;
                     }
diff --git a/src/librustc_mir/transform/check_consts/resolver.rs b/src/librustc_mir/transform/check_consts/resolver.rs
index 8909ef7db68..9004c5be987 100644
--- a/src/librustc_mir/transform/check_consts/resolver.rs
+++ b/src/librustc_mir/transform/check_consts/resolver.rs
@@ -77,7 +77,7 @@ where
         args: &[mir::Operand<'tcx>],
         return_place: &mir::Place<'tcx>,
     ) {
-        let return_ty = return_place.ty(self.item.body, self.item.tcx).ty;
+        let return_ty = return_place.ty(&*self.item.body, self.item.tcx).ty;
         let qualif = Q::in_call(
             self.item,
             &|l| self.qualifs_per_local.contains(l),
diff --git a/src/librustc_mir/transform/check_consts/validation.rs b/src/librustc_mir/transform/check_consts/validation.rs
index 783c64ece73..9d477bfbae8 100644
--- a/src/librustc_mir/transform/check_consts/validation.rs
+++ b/src/librustc_mir/transform/check_consts/validation.rs
@@ -39,9 +39,9 @@ impl<Q: Qualif> QualifCursor<'a, 'mir, 'tcx, Q> {
     ) -> Self {
         let analysis = FlowSensitiveAnalysis::new(q, item);
         let results =
-            dataflow::Engine::new(item.tcx, item.body, item.def_id, dead_unwinds, analysis)
+            dataflow::Engine::new(item.tcx, &item.body, item.def_id, dead_unwinds, analysis)
                 .iterate_to_fixpoint();
-        let cursor = dataflow::ResultsCursor::new(item.body, results);
+        let cursor = dataflow::ResultsCursor::new(item.body.body(), results);
 
         let mut in_any_value_of_ty = BitSet::new_empty(item.body.local_decls.len());
         for (local, decl) in item.body.local_decls.iter_enumerated() {
@@ -172,17 +172,17 @@ impl Validator<'a, 'mir, 'tcx> {
 
         let indirectly_mutable = old_dataflow::do_dataflow(
             item.tcx,
-            item.body,
+            &*item.body,
             item.def_id,
             &item.tcx.get_attrs(item.def_id),
             &dead_unwinds,
-            old_dataflow::IndirectlyMutableLocals::new(item.tcx, item.body, item.param_env),
+            old_dataflow::IndirectlyMutableLocals::new(item.tcx, item.body.body(), item.param_env),
             |_, local| old_dataflow::DebugFormatted::new(&local),
         );
 
         let indirectly_mutable = old_dataflow::DataflowResultsCursor::new(
             indirectly_mutable,
-            item.body,
+            item.body.body(),
         );
 
         let qualifs = Qualifs {
@@ -208,7 +208,7 @@ impl Validator<'a, 'mir, 'tcx> {
         if use_min_const_fn_checks {
             // Enforce `min_const_fn` for stable `const fn`s.
             use crate::transform::qualify_min_const_fn::is_min_const_fn;
-            if let Err((span, err)) = is_min_const_fn(tcx, def_id, body) {
+            if let Err((span, err)) = is_min_const_fn(tcx, def_id, &body) {
                 error_min_const_fn_violation(tcx, span, err);
                 return;
             }
@@ -230,7 +230,7 @@ impl Validator<'a, 'mir, 'tcx> {
 
         if should_check_for_sync {
             let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
-            check_return_ty_is_sync(tcx, body, hir_id);
+            check_return_ty_is_sync(tcx, &body, hir_id);
         }
     }
 
@@ -304,7 +304,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
 
         // Special-case reborrows to be more like a copy of a reference.
         if let Rvalue::Ref(_, kind, ref place) = *rvalue {
-            if let Some(reborrowed_proj) = place_as_reborrow(self.tcx, self.body, place) {
+            if let Some(reborrowed_proj) = place_as_reborrow(self.tcx, &*self.body, place) {
                 let ctx = match kind {
                     BorrowKind::Shared => PlaceContext::NonMutatingUse(
                         NonMutatingUseContext::SharedBorrow,
@@ -342,7 +342,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
             | Rvalue::Ref(_, kind @ BorrowKind::Mut { .. }, ref place)
             | Rvalue::Ref(_, kind @ BorrowKind::Unique, ref place)
             => {
-                let ty = place.ty(self.body, self.tcx).ty;
+                let ty = place.ty(&*self.body, self.tcx).ty;
                 let is_allowed = match ty.kind {
                     // Inside a `static mut`, `&mut [...]` is allowed.
                     ty::Array(..) | ty::Slice(_) if self.const_kind() == ConstKind::StaticMut
@@ -390,7 +390,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
             }
 
             Rvalue::Cast(CastKind::Misc, ref operand, cast_ty) => {
-                let operand_ty = operand.ty(self.body, self.tcx);
+                let operand_ty = operand.ty(&*self.body, self.tcx);
                 let cast_in = CastTy::from_ty(operand_ty).expect("bad input type for cast");
                 let cast_out = CastTy::from_ty(cast_ty).expect("bad output type for cast");
 
@@ -401,7 +401,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
             }
 
             Rvalue::BinaryOp(op, ref lhs, _) => {
-                if let ty::RawPtr(_) | ty::FnPtr(..) = lhs.ty(self.body, self.tcx).kind {
+                if let ty::RawPtr(_) | ty::FnPtr(..) = lhs.ty(&*self.body, self.tcx).kind {
                     assert!(op == BinOp::Eq || op == BinOp::Ne ||
                             op == BinOp::Le || op == BinOp::Lt ||
                             op == BinOp::Ge || op == BinOp::Gt ||
@@ -475,7 +475,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
 
         match elem {
             ProjectionElem::Deref => {
-                let base_ty = Place::ty_from(place_base, proj_base, self.body, self.tcx).ty;
+                let base_ty = Place::ty_from(place_base, proj_base, &*self.body, self.tcx).ty;
                 if let ty::RawPtr(_) = base_ty.kind {
                     if proj_base.is_empty() {
                         if let (PlaceBase::Local(local), []) = (place_base, proj_base) {
@@ -499,7 +499,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
             ProjectionElem::Subslice {..} |
             ProjectionElem::Field(..) |
             ProjectionElem::Index(_) => {
-                let base_ty = Place::ty_from(place_base, proj_base, self.body, self.tcx).ty;
+                let base_ty = Place::ty_from(place_base, proj_base, &*self.body, self.tcx).ty;
                 match base_ty.ty_adt_def() {
                     Some(def) if def.is_union() => {
                         self.check_op(ops::UnionAccess);
@@ -548,7 +548,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
 
         match kind {
             TerminatorKind::Call { func, .. } => {
-                let fn_ty = func.ty(self.body, self.tcx);
+                let fn_ty = func.ty(&*self.body, self.tcx);
 
                 let def_id = match fn_ty.kind {
                     ty::FnDef(def_id, _) => def_id,
@@ -609,7 +609,7 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> {
                 // Check to see if the type of this place can ever have a drop impl. If not, this
                 // `Drop` terminator is frivolous.
                 let ty_needs_drop = dropped_place
-                    .ty(self.body, self.tcx)
+                    .ty(&*self.body, self.tcx)
                     .ty
                     .needs_drop(self.tcx, self.param_env);
 
diff --git a/src/librustc_mir/transform/check_unsafety.rs b/src/librustc_mir/transform/check_unsafety.rs
index d12d21aee6a..2c45dcfbe26 100644
--- a/src/librustc_mir/transform/check_unsafety.rs
+++ b/src/librustc_mir/transform/check_unsafety.rs
@@ -528,6 +528,9 @@ fn unsafety_check_result(tcx: TyCtxt<'_>, def_id: DefId) -> UnsafetyCheckResult
         hir::BodyOwnerKind::Static(_) => (true, false),
     };
     let mut checker = UnsafetyChecker::new(const_context, min_const_fn, body, tcx, param_env);
+    // mir_built ensures that body has a computed cache, so we don't (and can't) attempt to
+    // recompute it here.
+    let body = body.unwrap_read_only();
     checker.visit_body(body);
 
     check_unused_unsafe(tcx, def_id, &checker.used_unsafe, &mut checker.inherited_blocks);
diff --git a/src/librustc_mir/transform/cleanup_post_borrowck.rs b/src/librustc_mir/transform/cleanup_post_borrowck.rs
index 4fd4fe45cd4..d9dd7c9d847 100644
--- a/src/librustc_mir/transform/cleanup_post_borrowck.rs
+++ b/src/librustc_mir/transform/cleanup_post_borrowck.rs
@@ -16,7 +16,7 @@
 //! [`FakeRead`]: rustc::mir::StatementKind::FakeRead
 //! [`Nop`]: rustc::mir::StatementKind::Nop
 
-use rustc::mir::{BorrowKind, Rvalue, Location, Body};
+use rustc::mir::{BodyCache, BorrowKind, Rvalue, Location};
 use rustc::mir::{Statement, StatementKind};
 use rustc::mir::visit::MutVisitor;
 use rustc::ty::TyCtxt;
@@ -29,7 +29,9 @@ pub struct DeleteNonCodegenStatements<'tcx> {
 }
 
 impl<'tcx> MirPass<'tcx> for CleanupNonCodegenStatements {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         let mut delete = DeleteNonCodegenStatements { tcx };
         delete.visit_body(body);
     }
diff --git a/src/librustc_mir/transform/const_prop.rs b/src/librustc_mir/transform/const_prop.rs
index bbbaac145f5..a99ca71d167 100644
--- a/src/librustc_mir/transform/const_prop.rs
+++ b/src/librustc_mir/transform/const_prop.rs
@@ -7,9 +7,10 @@ use std::cell::Cell;
 use rustc::hir::def::DefKind;
 use rustc::hir::def_id::DefId;
 use rustc::mir::{
-    AggregateKind, Constant, Location, Place, PlaceBase, Body, Operand, Rvalue, Local, UnOp,
-    StatementKind, Statement, LocalKind, TerminatorKind, Terminator,  ClearCrossCrate, SourceInfo,
-    BinOp, SourceScope, SourceScopeData, LocalDecl, BasicBlock, RETURN_PLACE,
+    AggregateKind, Constant, Location, Place, PlaceBase, Body, BodyCache, Operand, Local, UnOp,
+    Rvalue, StatementKind, Statement, LocalKind, TerminatorKind, Terminator,  ClearCrossCrate,
+    SourceInfo, BinOp, SourceScope, SourceScopeData, LocalDecl, BasicBlock, ReadOnlyBodyCache,
+    read_only, RETURN_PLACE
 };
 use rustc::mir::visit::{
     Visitor, PlaceContext, MutatingUseContext, MutVisitor, NonMutatingUseContext,
@@ -41,7 +42,9 @@ const MAX_ALLOC_LIMIT: u64 = 1024;
 pub struct ConstProp;
 
 impl<'tcx> MirPass<'tcx> for ConstProp {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         // will be evaluated by miri and produce its errors there
         if source.promoted.is_some() {
             return;
@@ -92,7 +95,7 @@ impl<'tcx> MirPass<'tcx> for ConstProp {
         // That would require an uniform one-def no-mutation analysis
         // and RPO (or recursing when needing the value of a local).
         let mut optimization_finder = ConstPropagator::new(
-            body,
+            read_only!(body),
             dummy_body,
             tcx,
             source
@@ -293,7 +296,7 @@ impl<'mir, 'tcx> HasTyCtxt<'tcx> for ConstPropagator<'mir, 'tcx> {
 
 impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> {
     fn new(
-        body: &Body<'tcx>,
+        body: ReadOnlyBodyCache<'_, 'tcx>,
         dummy_body: &'mir Body<'tcx>,
         tcx: TyCtxt<'tcx>,
         source: MirSource<'tcx>,
@@ -687,7 +690,7 @@ struct CanConstProp {
 
 impl CanConstProp {
     /// returns true if `local` can be propagated
-    fn check(body: &Body<'_>) -> IndexVec<Local, bool> {
+    fn check(body: ReadOnlyBodyCache<'_, '_>) -> IndexVec<Local, bool> {
         let mut cpv = CanConstProp {
             can_const_prop: IndexVec::from_elem(true, &body.local_decls),
             found_assignment: IndexVec::from_elem(false, &body.local_decls),
diff --git a/src/librustc_mir/transform/copy_prop.rs b/src/librustc_mir/transform/copy_prop.rs
index 4c26feac4af..5e4caf2f36d 100644
--- a/src/librustc_mir/transform/copy_prop.rs
+++ b/src/librustc_mir/transform/copy_prop.rs
@@ -19,7 +19,10 @@
 //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
 //! future.
 
-use rustc::mir::{Constant, Local, LocalKind, Location, Place, Body, Operand, Rvalue, StatementKind};
+use rustc::mir::{
+    Constant, Local, LocalKind, Location, Place, Body, BodyCache, Operand, Rvalue,
+    StatementKind, read_only
+};
 use rustc::mir::visit::MutVisitor;
 use rustc::ty::TyCtxt;
 use crate::transform::{MirPass, MirSource};
@@ -28,7 +31,9 @@ use crate::util::def_use::DefUseAnalysis;
 pub struct CopyPropagation;
 
 impl<'tcx> MirPass<'tcx> for CopyPropagation {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         // We only run when the MIR optimization level is > 1.
         // This avoids a slow pass, and messing up debug info.
         if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
@@ -37,10 +42,10 @@ impl<'tcx> MirPass<'tcx> for CopyPropagation {
 
         let mut def_use_analysis = DefUseAnalysis::new(body);
         loop {
-            def_use_analysis.analyze(body);
+            def_use_analysis.analyze(read_only!(body));
 
             if eliminate_self_assignments(body, &def_use_analysis) {
-                def_use_analysis.analyze(body);
+                def_use_analysis.analyze(read_only!(body));
             }
 
             let mut changed = false;
@@ -97,7 +102,10 @@ impl<'tcx> MirPass<'tcx> for CopyPropagation {
                                     let maybe_action = match operand {
                                         Operand::Copy(ref src_place) |
                                         Operand::Move(ref src_place) => {
-                                            Action::local_copy(&body, &def_use_analysis, src_place)
+                                            Action::local_copy(
+                                                &body,
+                                                &def_use_analysis,
+                                                src_place)
                                         }
                                         Operand::Constant(ref src_constant) => {
                                             Action::constant(src_constant)
@@ -126,8 +134,8 @@ impl<'tcx> MirPass<'tcx> for CopyPropagation {
                     }
                 }
 
-                changed =
-                    action.perform(body, &def_use_analysis, dest_local, location, tcx) || changed;
+                changed = action.perform(body, &def_use_analysis, dest_local, location, tcx)
+                    || changed;
                 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
                 // regenerating the chains.
                 break
@@ -242,7 +250,7 @@ impl<'tcx> Action<'tcx> {
     }
 
     fn perform(self,
-               body: &mut Body<'tcx>,
+               body: &mut BodyCache<'tcx>,
                def_use_analysis: &DefUseAnalysis,
                dest_local: Local,
                location: Location,
@@ -270,7 +278,8 @@ impl<'tcx> Action<'tcx> {
                 }
 
                 // Replace all uses of the destination local with the source local.
-                def_use_analysis.replace_all_defs_and_uses_with(dest_local, body, src_local, tcx);
+                def_use_analysis
+                    .replace_all_defs_and_uses_with(dest_local, body, src_local, tcx);
 
                 // Finally, zap the now-useless assignment instruction.
                 debug!("  Deleting assignment");
diff --git a/src/librustc_mir/transform/deaggregator.rs b/src/librustc_mir/transform/deaggregator.rs
index cdde9e12edc..933936e7eff 100644
--- a/src/librustc_mir/transform/deaggregator.rs
+++ b/src/librustc_mir/transform/deaggregator.rs
@@ -6,7 +6,9 @@ use crate::util::expand_aggregate;
 pub struct Deaggregator;
 
 impl<'tcx> MirPass<'tcx> for Deaggregator {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         let (basic_blocks, local_decls) = body.basic_blocks_and_local_decls_mut();
         let local_decls = &*local_decls;
         for bb in basic_blocks {
diff --git a/src/librustc_mir/transform/dump_mir.rs b/src/librustc_mir/transform/dump_mir.rs
index ed0eff943a1..13b3bb6da4e 100644
--- a/src/librustc_mir/transform/dump_mir.rs
+++ b/src/librustc_mir/transform/dump_mir.rs
@@ -5,7 +5,7 @@ use std::fmt;
 use std::fs::File;
 use std::io;
 
-use rustc::mir::Body;
+use rustc::mir::{Body, BodyCache};
 use rustc::session::config::{OutputFilenames, OutputType};
 use rustc::ty::TyCtxt;
 use crate::transform::{MirPass, MirSource};
@@ -18,8 +18,9 @@ impl<'tcx> MirPass<'tcx> for Marker {
         Cow::Borrowed(self.0)
     }
 
-    fn run_pass(&self, _tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, _body: &mut Body<'tcx>) {
-    }
+    fn run_pass(
+        &self, _tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, _body: &mut BodyCache<'tcx>
+    ) {}
 }
 
 pub struct Disambiguator {
diff --git a/src/librustc_mir/transform/elaborate_drops.rs b/src/librustc_mir/transform/elaborate_drops.rs
index f91a08bcd9a..42daba93bd2 100644
--- a/src/librustc_mir/transform/elaborate_drops.rs
+++ b/src/librustc_mir/transform/elaborate_drops.rs
@@ -21,7 +21,7 @@ use syntax_pos::Span;
 pub struct ElaborateDrops;
 
 impl<'tcx> MirPass<'tcx> for ElaborateDrops {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         debug!("elaborate_drops({:?} @ {:?})", src, body.span);
 
         let def_id = src.def_id();
diff --git a/src/librustc_mir/transform/erase_regions.rs b/src/librustc_mir/transform/erase_regions.rs
index b30e2de4ca0..882e67432a5 100644
--- a/src/librustc_mir/transform/erase_regions.rs
+++ b/src/librustc_mir/transform/erase_regions.rs
@@ -62,7 +62,7 @@ impl MutVisitor<'tcx> for EraseRegionsVisitor<'tcx> {
 pub struct EraseRegions;
 
 impl<'tcx> MirPass<'tcx> for EraseRegions {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         EraseRegionsVisitor::new(tcx).visit_body(body);
     }
 }
diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs
index 5d88629435b..e55737e8859 100644
--- a/src/librustc_mir/transform/generator.rs
+++ b/src/librustc_mir/transform/generator.rs
@@ -368,7 +368,7 @@ impl MutVisitor<'tcx> for TransformVisitor<'tcx> {
                 VariantIdx::new(RETURNED) // state for returned
             };
             data.statements.push(self.set_discr(state, source_info));
-            data.terminator.as_mut().unwrap().kind = TerminatorKind::Return;
+            data.terminator_mut().kind = TerminatorKind::Return;
         }
 
         self.super_basic_block_data(block, data);
@@ -378,7 +378,7 @@ impl MutVisitor<'tcx> for TransformVisitor<'tcx> {
 fn make_generator_state_argument_indirect<'tcx>(
     tcx: TyCtxt<'tcx>,
     def_id: DefId,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
 ) {
     let gen_ty = body.local_decls.raw[1].ty;
 
@@ -401,7 +401,7 @@ fn make_generator_state_argument_indirect<'tcx>(
     DerefArgVisitor { tcx }.visit_body(body);
 }
 
-fn make_generator_state_argument_pinned<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
+fn make_generator_state_argument_pinned<'tcx>(tcx: TyCtxt<'tcx>, body: &mut BodyCache<'tcx>) {
     let ref_gen_ty = body.local_decls.raw[1].ty;
 
     let pin_did = tcx.lang_items().pin_type().unwrap();
@@ -418,7 +418,7 @@ fn make_generator_state_argument_pinned<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body
 
 fn replace_result_variable<'tcx>(
     ret_ty: Ty<'tcx>,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     tcx: TyCtxt<'tcx>,
 ) -> Local {
     let source_info = source_info(body);
@@ -481,20 +481,21 @@ struct LivenessInfo {
 
 fn locals_live_across_suspend_points(
     tcx: TyCtxt<'tcx>,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     source: MirSource<'tcx>,
     movable: bool,
 ) -> LivenessInfo {
     let dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
     let def_id = source.def_id();
+    let body_ref: &Body<'_> = &body;
 
     // Calculate when MIR locals have live storage. This gives us an upper bound of their
     // lifetimes.
-    let storage_live_analysis = MaybeStorageLive::new(body);
+    let storage_live_analysis = MaybeStorageLive::new(body_ref);
     let storage_live_results =
-        do_dataflow(tcx, body, def_id, &[], &dead_unwinds, storage_live_analysis,
+        do_dataflow(tcx, body_ref, def_id, &[], &dead_unwinds, storage_live_analysis,
                     |bd, p| DebugFormatted::new(&bd.body().local_decls[p]));
-    let mut storage_live_cursor = DataflowResultsCursor::new(&storage_live_results, body);
+    let mut storage_live_cursor = DataflowResultsCursor::new(&storage_live_results, body_ref);
 
     // Find the MIR locals which do not use StorageLive/StorageDead statements.
     // The storage of these locals are always live.
@@ -503,19 +504,20 @@ fn locals_live_across_suspend_points(
 
     // Calculate the MIR locals which have been previously
     // borrowed (even if they are still active).
-    let borrowed_locals_analysis = HaveBeenBorrowedLocals::new(body);
+    let borrowed_locals_analysis = HaveBeenBorrowedLocals::new(body_ref);
     let borrowed_locals_results =
-        do_dataflow(tcx, body, def_id, &[], &dead_unwinds, borrowed_locals_analysis,
+        do_dataflow(tcx, body_ref, def_id, &[], &dead_unwinds, borrowed_locals_analysis,
                     |bd, p| DebugFormatted::new(&bd.body().local_decls[p]));
-    let mut borrowed_locals_cursor = DataflowResultsCursor::new(&borrowed_locals_results, body);
+    let mut borrowed_locals_cursor = DataflowResultsCursor::new(&borrowed_locals_results, body_ref);
 
     // Calculate the MIR locals that we actually need to keep storage around
     // for.
     let requires_storage_analysis = RequiresStorage::new(body, &borrowed_locals_results);
     let requires_storage_results =
-        do_dataflow(tcx, body, def_id, &[], &dead_unwinds, requires_storage_analysis,
+        do_dataflow(tcx, body_ref, def_id, &[], &dead_unwinds, requires_storage_analysis,
                     |bd, p| DebugFormatted::new(&bd.body().local_decls[p]));
-    let mut requires_storage_cursor = DataflowResultsCursor::new(&requires_storage_results, body);
+    let mut requires_storage_cursor
+        = DataflowResultsCursor::new(&requires_storage_results, body_ref);
 
     // Calculate the liveness of MIR locals ignoring borrows.
     let mut live_locals = liveness::LiveVarSet::new_empty(body.local_decls.len());
@@ -526,7 +528,7 @@ fn locals_live_across_suspend_points(
         tcx,
         "generator_liveness",
         source,
-        body,
+        body_ref,
         &liveness,
     );
 
@@ -593,7 +595,7 @@ fn locals_live_across_suspend_points(
         .collect();
 
     let storage_conflicts = compute_storage_conflicts(
-        body,
+        body_ref,
         &live_locals,
         &ignored,
         requires_storage_results);
@@ -749,7 +751,7 @@ fn compute_layout<'tcx>(
     upvars: &Vec<Ty<'tcx>>,
     interior: Ty<'tcx>,
     movable: bool,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
 ) -> (
     FxHashMap<Local, (Ty<'tcx>, VariantIdx, usize)>,
     GeneratorLayout<'tcx>,
@@ -758,7 +760,7 @@ fn compute_layout<'tcx>(
     // Use a liveness analysis to compute locals which are live across a suspension point
     let LivenessInfo {
         live_locals, live_locals_at_suspension_points, storage_conflicts, storage_liveness
-    } = locals_live_across_suspend_points(tcx, body, source, movable);
+    } = locals_live_across_suspend_points(tcx, read_only!(body), source, movable);
 
     // Erase regions from the types passed in from typeck so we can compare them with
     // MIR types
@@ -828,7 +830,7 @@ fn compute_layout<'tcx>(
 }
 
 fn insert_switch<'tcx>(
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     cases: Vec<(usize, BasicBlock)>,
     transform: &TransformVisitor<'tcx>,
     default: TerminatorKind<'tcx>,
@@ -859,7 +861,9 @@ fn insert_switch<'tcx>(
     }
 }
 
-fn elaborate_generator_drops<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, body: &mut Body<'tcx>) {
+fn elaborate_generator_drops<'tcx>(
+    tcx: TyCtxt<'tcx>, def_id: DefId, body: &mut BodyCache<'tcx>
+) {
     use crate::util::elaborate_drops::{elaborate_drop, Unwind};
     use crate::util::patch::MirPatch;
     use crate::shim::DropShimElaborator;
@@ -872,7 +876,7 @@ fn elaborate_generator_drops<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, body: &mut
     let gen = self_arg();
 
     let mut elaborator = DropShimElaborator {
-        body: body,
+        body,
         patch: MirPatch::new(body),
         tcx,
         param_env
@@ -924,9 +928,9 @@ fn create_generator_drop_shim<'tcx>(
     def_id: DefId,
     source: MirSource<'tcx>,
     gen_ty: Ty<'tcx>,
-    body: &Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     drop_clean: BasicBlock,
-) -> Body<'tcx> {
+) -> BodyCache<'tcx> {
     let mut body = body.clone();
 
     let source_info = source_info(&body);
@@ -992,7 +996,9 @@ fn create_generator_drop_shim<'tcx>(
     body
 }
 
-fn insert_term_block<'tcx>(body: &mut Body<'tcx>, kind: TerminatorKind<'tcx>) -> BasicBlock {
+fn insert_term_block<'tcx>(
+    body: &mut BodyCache<'tcx>, kind: TerminatorKind<'tcx>
+) -> BasicBlock {
     let term_block = BasicBlock::new(body.basic_blocks().len());
     let source_info = source_info(body);
     body.basic_blocks_mut().push(BasicBlockData {
@@ -1008,7 +1014,7 @@ fn insert_term_block<'tcx>(body: &mut Body<'tcx>, kind: TerminatorKind<'tcx>) ->
 
 fn insert_panic_block<'tcx>(
     tcx: TyCtxt<'tcx>,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     message: AssertMessage<'tcx>,
 ) -> BasicBlock {
     let assert_block = BasicBlock::new(body.basic_blocks().len());
@@ -1042,7 +1048,7 @@ fn create_generator_resume_function<'tcx>(
     transform: TransformVisitor<'tcx>,
     def_id: DefId,
     source: MirSource<'tcx>,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
 ) {
     // Poison the generator when it unwinds
     for block in body.basic_blocks_mut() {
@@ -1095,7 +1101,7 @@ fn source_info(body: &Body<'_>) -> SourceInfo {
     }
 }
 
-fn insert_clean_drop(body: &mut Body<'_>) -> BasicBlock {
+fn insert_clean_drop(body: &mut BodyCache<'_>) -> BasicBlock {
     let return_block = insert_term_block(body, TerminatorKind::Return);
 
     // Create a block to destroy an unresumed generators. This can only destroy upvars.
@@ -1119,7 +1125,7 @@ fn insert_clean_drop(body: &mut Body<'_>) -> BasicBlock {
 }
 
 fn create_cases<'tcx, F>(
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     transform: &TransformVisitor<'tcx>,
     target: F,
 ) -> Vec<(usize, BasicBlock)>
@@ -1163,7 +1169,9 @@ where
 }
 
 impl<'tcx> MirPass<'tcx> for StateTransform {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         let yield_ty = if let Some(yield_ty) = body.yield_ty {
             yield_ty
         } else {
@@ -1252,12 +1260,12 @@ impl<'tcx> MirPass<'tcx> for StateTransform {
 
         // Create a copy of our MIR and use it to create the drop shim for the generator
         let drop_shim = create_generator_drop_shim(tcx,
-            &transform,
-            def_id,
-            source,
-            gen_ty,
-            &body,
-            drop_clean);
+                                                   &transform,
+                                                   def_id,
+                                                   source,
+                                                   gen_ty,
+                                                   body,
+                                                   drop_clean);
 
         body.generator_drop = Some(box drop_shim);
 
diff --git a/src/librustc_mir/transform/inline.rs b/src/librustc_mir/transform/inline.rs
index ebfadd0cfd3..79cb7fb0b76 100644
--- a/src/librustc_mir/transform/inline.rs
+++ b/src/librustc_mir/transform/inline.rs
@@ -38,7 +38,9 @@ struct CallSite<'tcx> {
 }
 
 impl<'tcx> MirPass<'tcx> for Inline {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         if tcx.sess.opts.debugging_opts.mir_opt_level >= 2 {
             Inliner { tcx, source }.run_pass(body);
         }
@@ -51,7 +53,7 @@ struct Inliner<'tcx> {
 }
 
 impl Inliner<'tcx> {
-    fn run_pass(&self, caller_body: &mut Body<'tcx>) {
+    fn run_pass(&self, caller_body: &mut BodyCache<'tcx>) {
         // Keep a queue of callsites to try inlining on. We take
         // advantage of the fact that queries detect cycles here to
         // allow us to try and fetch the fully optimized MIR of a
@@ -75,9 +77,9 @@ impl Inliner<'tcx> {
         {
             for (bb, bb_data) in caller_body.basic_blocks().iter_enumerated() {
                 if let Some(callsite) = self.get_valid_function_call(bb,
-                                                                    bb_data,
-                                                                    caller_body,
-                                                                    param_env) {
+                                                                     bb_data,
+                                                                     caller_body,
+                                                                     param_env) {
                     callsites.push_back(callsite);
                 }
             }
@@ -136,7 +138,8 @@ impl Inliner<'tcx> {
                 debug!("attempting to inline callsite {:?} - success", callsite);
 
                 // Add callsites from inlined function
-                for (bb, bb_data) in caller_body.basic_blocks().iter_enumerated().skip(start) {
+                for (bb, bb_data) in caller_body.basic_blocks().iter_enumerated().skip(start)
+                {
                     if let Some(new_callsite) = self.get_valid_function_call(bb,
                                                                              bb_data,
                                                                              caller_body,
@@ -377,8 +380,8 @@ impl Inliner<'tcx> {
 
     fn inline_call(&self,
                    callsite: CallSite<'tcx>,
-                   caller_body: &mut Body<'tcx>,
-                   mut callee_body: Body<'tcx>) -> bool {
+                   caller_body: &mut BodyCache<'tcx>,
+                   mut callee_body: BodyCache<'tcx>) -> bool {
         let terminator = caller_body[callsite.bb].terminator.take().unwrap();
         match terminator.kind {
             // FIXME: Handle inlining of diverging calls
@@ -445,7 +448,7 @@ impl Inliner<'tcx> {
                         BorrowKind::Mut { allow_two_phase_borrow: false },
                         destination.0);
 
-                    let ty = dest.ty(caller_body, self.tcx);
+                    let ty = dest.ty(&**caller_body, self.tcx);
 
                     let temp = LocalDecl::new_temp(ty, callsite.location.span);
 
@@ -514,7 +517,7 @@ impl Inliner<'tcx> {
         &self,
         args: Vec<Operand<'tcx>>,
         callsite: &CallSite<'tcx>,
-        caller_body: &mut Body<'tcx>,
+        caller_body: &mut BodyCache<'tcx>,
     ) -> Vec<Local> {
         let tcx = self.tcx;
 
@@ -543,12 +546,14 @@ impl Inliner<'tcx> {
         // and the vector is `[closure_ref, tmp0, tmp1, tmp2]`.
         if tcx.is_closure(callsite.callee) {
             let mut args = args.into_iter();
-            let self_ = self.create_temp_if_necessary(args.next().unwrap(), callsite, caller_body);
-            let tuple = self.create_temp_if_necessary(args.next().unwrap(), callsite, caller_body);
+            let self_
+                = self.create_temp_if_necessary(args.next().unwrap(), callsite, caller_body);
+            let tuple
+                = self.create_temp_if_necessary(args.next().unwrap(), callsite, caller_body);
             assert!(args.next().is_none());
 
             let tuple = Place::from(tuple);
-            let tuple_tys = if let ty::Tuple(s) = tuple.ty(caller_body, tcx).ty.kind {
+            let tuple_tys = if let ty::Tuple(s) = tuple.ty(&**caller_body, tcx).ty.kind {
                 s
             } else {
                 bug!("Closure arguments are not passed as a tuple");
@@ -585,7 +590,7 @@ impl Inliner<'tcx> {
         &self,
         arg: Operand<'tcx>,
         callsite: &CallSite<'tcx>,
-        caller_body: &mut Body<'tcx>,
+        caller_body: &mut BodyCache<'tcx>,
     ) -> Local {
         // FIXME: Analysis of the usage of the arguments to avoid
         // unnecessary temporaries.
@@ -603,7 +608,7 @@ impl Inliner<'tcx> {
         // Otherwise, create a temporary for the arg
         let arg = Rvalue::Use(arg);
 
-        let ty = arg.ty(caller_body, self.tcx);
+        let ty = arg.ty(&**caller_body, self.tcx);
 
         let arg_tmp = LocalDecl::new_temp(ty, callsite.location.span);
         let arg_tmp = caller_body.local_decls.push(arg_tmp);
diff --git a/src/librustc_mir/transform/instcombine.rs b/src/librustc_mir/transform/instcombine.rs
index a567ed668bf..bd237b58132 100644
--- a/src/librustc_mir/transform/instcombine.rs
+++ b/src/librustc_mir/transform/instcombine.rs
@@ -1,7 +1,8 @@
 //! Performs various peephole optimizations.
 
 use rustc::mir::{
-    Constant, Location, Place, PlaceBase, PlaceRef, Body, Operand, ProjectionElem, Rvalue, Local
+    Constant, Location, Place, PlaceBase, PlaceRef, Body, BodyCache, Operand, ProjectionElem,
+    Rvalue, Local, read_only
 };
 use rustc::mir::visit::{MutVisitor, Visitor};
 use rustc::ty::{self, TyCtxt};
@@ -13,7 +14,7 @@ use crate::transform::{MirPass, MirSource};
 pub struct InstCombine;
 
 impl<'tcx> MirPass<'tcx> for InstCombine {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         // We only run when optimizing MIR (at any level).
         if tcx.sess.opts.debugging_opts.mir_opt_level == 0 {
             return
@@ -23,8 +24,9 @@ impl<'tcx> MirPass<'tcx> for InstCombine {
         // read-only so that we can do global analyses on the MIR in the process (e.g.
         // `Place::ty()`).
         let optimizations = {
+            let read_only_cache = read_only!(body);
             let mut optimization_finder = OptimizationFinder::new(body, tcx);
-            optimization_finder.visit_body(body);
+            optimization_finder.visit_body(read_only_cache);
             optimization_finder.optimizations
         };
 
diff --git a/src/librustc_mir/transform/mod.rs b/src/librustc_mir/transform/mod.rs
index 2b2b52971ef..df4cb761533 100644
--- a/src/librustc_mir/transform/mod.rs
+++ b/src/librustc_mir/transform/mod.rs
@@ -1,7 +1,7 @@
 use crate::{build, shim};
 use rustc_index::vec::IndexVec;
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
-use rustc::mir::{Body, MirPhase, Promoted, ConstQualifs};
+use rustc::mir::{BodyCache, MirPhase, Promoted, ConstQualifs};
 use rustc::ty::{TyCtxt, InstanceDef, TypeFoldable};
 use rustc::ty::query::Providers;
 use rustc::ty::steal::Steal;
@@ -97,7 +97,7 @@ fn mir_keys(tcx: TyCtxt<'_>, krate: CrateNum) -> &DefIdSet {
     tcx.arena.alloc(set)
 }
 
-fn mir_built(tcx: TyCtxt<'_>, def_id: DefId) -> &Steal<Body<'_>> {
+fn mir_built(tcx: TyCtxt<'_>, def_id: DefId) -> &Steal<BodyCache<'_>> {
     let mir = build::mir_build(tcx, def_id);
     tcx.alloc_steal_mir(mir)
 }
@@ -144,12 +144,12 @@ pub trait MirPass<'tcx> {
         default_name::<Self>()
     }
 
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>);
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyCache<'tcx>);
 }
 
 pub fn run_passes(
     tcx: TyCtxt<'tcx>,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     instance: InstanceDef<'tcx>,
     promoted: Option<Promoted>,
     mir_phase: MirPhase,
@@ -205,7 +205,7 @@ fn mir_const_qualif(tcx: TyCtxt<'_>, def_id: DefId) -> ConstQualifs {
     }
 
     let item = check_consts::Item {
-        body,
+        body: body.unwrap_read_only(),
         tcx,
         def_id,
         const_kind,
@@ -220,7 +220,7 @@ fn mir_const_qualif(tcx: TyCtxt<'_>, def_id: DefId) -> ConstQualifs {
     validator.qualifs_in_return_place().into()
 }
 
-fn mir_const(tcx: TyCtxt<'_>, def_id: DefId) -> &Steal<Body<'_>> {
+fn mir_const(tcx: TyCtxt<'_>, def_id: DefId) -> &Steal<BodyCache<'_>> {
     // Unsafety check uses the raw mir, so make sure it is run
     let _ = tcx.unsafety_check_result(def_id);
 
@@ -231,13 +231,14 @@ fn mir_const(tcx: TyCtxt<'_>, def_id: DefId) -> &Steal<Body<'_>> {
         &rustc_peek::SanityCheck,
         &uniform_array_move_out::UniformArrayMoveOut,
     ]);
+    body.ensure_predecessors();
     tcx.alloc_steal_mir(body)
 }
 
 fn mir_validated(
     tcx: TyCtxt<'tcx>,
     def_id: DefId,
-) -> (&'tcx Steal<Body<'tcx>>, &'tcx Steal<IndexVec<Promoted, Body<'tcx>>>) {
+) -> (&'tcx Steal<BodyCache<'tcx>>, &'tcx Steal<IndexVec<Promoted, BodyCache<'tcx>>>) {
     // Ensure that we compute the `mir_const_qualif` for constants at
     // this point, before we steal the mir-const result.
     let _ = tcx.mir_const_qualif(def_id);
@@ -249,13 +250,14 @@ fn mir_validated(
         &promote_pass,
         &simplify::SimplifyCfg::new("qualify-consts"),
     ]);
+
     let promoted = promote_pass.promoted_fragments.into_inner();
     (tcx.alloc_steal_mir(body), tcx.alloc_steal_promoted(promoted))
 }
 
 fn run_optimization_passes<'tcx>(
     tcx: TyCtxt<'tcx>,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     def_id: DefId,
     promoted: Option<Promoted>,
 ) {
@@ -317,7 +319,7 @@ fn run_optimization_passes<'tcx>(
     ]);
 }
 
-fn optimized_mir(tcx: TyCtxt<'_>, def_id: DefId) -> &Body<'_> {
+fn optimized_mir(tcx: TyCtxt<'_>, def_id: DefId) -> &BodyCache<'_> {
     if tcx.is_constructor(def_id) {
         // There's no reason to run all of the MIR passes on constructors when
         // we can just output the MIR we want directly. This also saves const
@@ -333,10 +335,11 @@ fn optimized_mir(tcx: TyCtxt<'_>, def_id: DefId) -> &Body<'_> {
     let (body, _) = tcx.mir_validated(def_id);
     let mut body = body.steal();
     run_optimization_passes(tcx, &mut body, def_id, None);
+    body.ensure_predecessors();
     tcx.arena.alloc(body)
 }
 
-fn promoted_mir<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> &'tcx IndexVec<Promoted, Body<'tcx>> {
+fn promoted_mir(tcx: TyCtxt<'_>, def_id: DefId) -> &IndexVec<Promoted, BodyCache<'_>> {
     if tcx.is_constructor(def_id) {
         return tcx.intern_promoted(IndexVec::new());
     }
@@ -347,6 +350,7 @@ fn promoted_mir<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> &'tcx IndexVec<Promot
 
     for (p, mut body) in promoted.iter_enumerated_mut() {
         run_optimization_passes(tcx, &mut body, def_id, Some(p));
+        body.ensure_predecessors();
     }
 
     tcx.intern_promoted(promoted)
diff --git a/src/librustc_mir/transform/no_landing_pads.rs b/src/librustc_mir/transform/no_landing_pads.rs
index fbd14d9ef61..5e1d29d47ad 100644
--- a/src/librustc_mir/transform/no_landing_pads.rs
+++ b/src/librustc_mir/transform/no_landing_pads.rs
@@ -17,12 +17,12 @@ impl<'tcx> NoLandingPads<'tcx> {
 }
 
 impl<'tcx> MirPass<'tcx> for NoLandingPads<'tcx> {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         no_landing_pads(tcx, body)
     }
 }
 
-pub fn no_landing_pads<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
+pub fn no_landing_pads<'tcx>(tcx: TyCtxt<'tcx>, body: &mut BodyCache<'tcx>) {
     if tcx.sess.no_landing_pads() {
         NoLandingPads::new(tcx).visit_body(body);
     }
diff --git a/src/librustc_mir/transform/promote_consts.rs b/src/librustc_mir/transform/promote_consts.rs
index 591f3ca4400..c99824bd356 100644
--- a/src/librustc_mir/transform/promote_consts.rs
+++ b/src/librustc_mir/transform/promote_consts.rs
@@ -41,11 +41,11 @@ use crate::transform::check_consts::{qualifs, Item, ConstKind, is_lang_panic_fn}
 /// newly created `StaticKind::Promoted`.
 #[derive(Default)]
 pub struct PromoteTemps<'tcx> {
-    pub promoted_fragments: Cell<IndexVec<Promoted, Body<'tcx>>>,
+    pub promoted_fragments: Cell<IndexVec<Promoted, BodyCache<'tcx>>>,
 }
 
 impl<'tcx> MirPass<'tcx> for PromoteTemps<'tcx> {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         // There's not really any point in promoting errorful MIR.
         //
         // This does not include MIR that failed const-checking, which we still try to promote.
@@ -63,7 +63,8 @@ impl<'tcx> MirPass<'tcx> for PromoteTemps<'tcx> {
         let mut rpo = traversal::reverse_postorder(body);
         let (temps, all_candidates) = collect_temps_and_candidates(tcx, body, &mut rpo);
 
-        let promotable_candidates = validate_candidates(tcx, body, def_id, &temps, &all_candidates);
+        let promotable_candidates
+            = validate_candidates(tcx, read_only!(body), def_id, &temps, &all_candidates);
 
         let promoted = promote_candidates(def_id, body, tcx, temps, promotable_candidates);
         self.promoted_fragments.set(promoted);
@@ -346,10 +347,14 @@ impl<'tcx> Validator<'_, 'tcx> {
                             while let [proj_base @ .., elem] = place_projection {
                                 // FIXME(eddyb) this is probably excessive, with
                                 // the exception of `union` member accesses.
-                                let ty =
-                                    Place::ty_from(&place.base, proj_base, self.body, self.tcx)
-                                        .projection_ty(self.tcx, elem)
-                                        .ty;
+                                let ty = Place::ty_from(
+                                        &place.base,
+                                        proj_base,
+                                        &*self.body,
+                                        self.tcx
+                                    )
+                                    .projection_ty(self.tcx, elem)
+                                    .ty;
                                 if ty.is_freeze(self.tcx, self.param_env, DUMMY_SP) {
                                     has_mut_interior = false;
                                     break;
@@ -368,7 +373,7 @@ impl<'tcx> Validator<'_, 'tcx> {
                         }
 
                         if let BorrowKind::Mut { .. } = kind {
-                            let ty = place.ty(self.body, self.tcx).ty;
+                            let ty = place.ty(&*self.body, self.tcx).ty;
 
                             // In theory, any zero-sized value could be borrowed
                             // mutably without consequences. However, only &mut []
@@ -517,7 +522,7 @@ impl<'tcx> Validator<'_, 'tcx> {
                     ProjectionElem::Field(..) => {
                         if self.const_kind.is_none() {
                             let base_ty =
-                                Place::ty_from(place.base, proj_base, self.body, self.tcx).ty;
+                                Place::ty_from(place.base, proj_base, &*self.body, self.tcx).ty;
                             if let Some(def) = base_ty.ty_adt_def() {
                                 // No promotion of union field accesses.
                                 if def.is_union() {
@@ -566,7 +571,7 @@ impl<'tcx> Validator<'_, 'tcx> {
     fn validate_rvalue(&self, rvalue: &Rvalue<'tcx>) -> Result<(), Unpromotable> {
         match *rvalue {
             Rvalue::Cast(CastKind::Misc, ref operand, cast_ty) if self.const_kind.is_none() => {
-                let operand_ty = operand.ty(self.body, self.tcx);
+                let operand_ty = operand.ty(&*self.body, self.tcx);
                 let cast_in = CastTy::from_ty(operand_ty).expect("bad input type for cast");
                 let cast_out = CastTy::from_ty(cast_ty).expect("bad output type for cast");
                 match (cast_in, cast_out) {
@@ -580,7 +585,7 @@ impl<'tcx> Validator<'_, 'tcx> {
             }
 
             Rvalue::BinaryOp(op, ref lhs, _) if self.const_kind.is_none() => {
-                if let ty::RawPtr(_) | ty::FnPtr(..) = lhs.ty(self.body, self.tcx).kind {
+                if let ty::RawPtr(_) | ty::FnPtr(..) = lhs.ty(&*self.body, self.tcx).kind {
                     assert!(op == BinOp::Eq || op == BinOp::Ne ||
                             op == BinOp::Le || op == BinOp::Lt ||
                             op == BinOp::Ge || op == BinOp::Gt ||
@@ -615,7 +620,7 @@ impl<'tcx> Validator<'_, 'tcx> {
 
             Rvalue::Ref(_, kind, place) => {
                 if let BorrowKind::Mut { .. } = kind {
-                    let ty = place.ty(self.body, self.tcx).ty;
+                    let ty = place.ty(&*self.body, self.tcx).ty;
 
                     // In theory, any zero-sized value could be borrowed
                     // mutably without consequences. However, only &mut []
@@ -642,7 +647,7 @@ impl<'tcx> Validator<'_, 'tcx> {
                 let mut place = place.as_ref();
                 if let [proj_base @ .., ProjectionElem::Deref] = &place.projection {
                     let base_ty =
-                        Place::ty_from(&place.base, proj_base, self.body, self.tcx).ty;
+                        Place::ty_from(&place.base, proj_base, &*self.body, self.tcx).ty;
                     if let ty::Ref(..) = base_ty.kind {
                         place = PlaceRef {
                             base: &place.base,
@@ -668,7 +673,7 @@ impl<'tcx> Validator<'_, 'tcx> {
                     while let [proj_base @ .., elem] = place_projection {
                         // FIXME(eddyb) this is probably excessive, with
                         // the exception of `union` member accesses.
-                        let ty = Place::ty_from(place.base, proj_base, self.body, self.tcx)
+                        let ty = Place::ty_from(place.base, proj_base, &*self.body, self.tcx)
                             .projection_ty(self.tcx, elem)
                             .ty;
                         if ty.is_freeze(self.tcx, self.param_env, DUMMY_SP) {
@@ -701,7 +706,7 @@ impl<'tcx> Validator<'_, 'tcx> {
         callee: &Operand<'tcx>,
         args: &[Operand<'tcx>],
     ) -> Result<(), Unpromotable> {
-        let fn_ty = callee.ty(self.body, self.tcx);
+        let fn_ty = callee.ty(&*self.body, self.tcx);
 
         if !self.explicit && self.const_kind.is_none() {
             if let ty::FnDef(def_id, _) = fn_ty.kind {
@@ -737,7 +742,7 @@ impl<'tcx> Validator<'_, 'tcx> {
 // FIXME(eddyb) remove the differences for promotability in `static`, `const`, `const fn`.
 pub fn validate_candidates(
     tcx: TyCtxt<'tcx>,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     def_id: DefId,
     temps: &IndexVec<Local, TempState>,
     candidates: &[Candidate],
@@ -770,8 +775,8 @@ pub fn validate_candidates(
 
 struct Promoter<'a, 'tcx> {
     tcx: TyCtxt<'tcx>,
-    source: &'a mut Body<'tcx>,
-    promoted: Body<'tcx>,
+    source: &'a mut BodyCache<'tcx>,
+    promoted: BodyCache<'tcx>,
     temps: &'a mut IndexVec<Local, TempState>,
 
     /// If true, all nested temps are also kept in the
@@ -919,7 +924,7 @@ impl<'a, 'tcx> Promoter<'a, 'tcx> {
         def_id: DefId,
         candidate: Candidate,
         next_promoted_id: usize,
-    ) -> Option<Body<'tcx>> {
+    ) -> Option<BodyCache<'tcx>> {
         let mut operand = {
             let promoted = &mut self.promoted;
             let promoted_id = Promoted::new(next_promoted_id);
@@ -1040,11 +1045,11 @@ impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> {
 
 pub fn promote_candidates<'tcx>(
     def_id: DefId,
-    body: &mut Body<'tcx>,
+    body: &mut BodyCache<'tcx>,
     tcx: TyCtxt<'tcx>,
     mut temps: IndexVec<Local, TempState>,
     candidates: Vec<Candidate>,
-) -> IndexVec<Promoted, Body<'tcx>> {
+) -> IndexVec<Promoted, BodyCache<'tcx>> {
     // Visit candidates in reverse, in case they're nested.
     debug!("promote_candidates({:?})", candidates);
 
@@ -1076,7 +1081,7 @@ pub fn promote_candidates<'tcx>(
         ).collect();
 
         let promoter = Promoter {
-            promoted: Body::new(
+            promoted: BodyCache::new(Body::new(
                 IndexVec::new(),
                 // FIXME: maybe try to filter this to avoid blowing up
                 // memory usage?
@@ -1088,7 +1093,7 @@ pub fn promote_candidates<'tcx>(
                 body.span,
                 vec![],
                 body.generator_kind,
-            ),
+            )),
             tcx,
             source: body,
             temps: &mut temps,
@@ -1145,11 +1150,11 @@ pub fn promote_candidates<'tcx>(
 crate fn should_suggest_const_in_array_repeat_expressions_attribute<'tcx>(
     tcx: TyCtxt<'tcx>,
     mir_def_id: DefId,
-    body: &Body<'tcx>,
+    body: ReadOnlyBodyCache<'_, 'tcx>,
     operand: &Operand<'tcx>,
 ) -> bool {
-    let mut rpo = traversal::reverse_postorder(body);
-    let (temps, _) = collect_temps_and_candidates(tcx, body, &mut rpo);
+    let mut rpo = traversal::reverse_postorder(&body);
+    let (temps, _) = collect_temps_and_candidates(tcx, &body, &mut rpo);
     let validator = Validator {
         item: Item::new(tcx, mir_def_id, body),
         temps: &temps,
diff --git a/src/librustc_mir/transform/remove_noop_landing_pads.rs b/src/librustc_mir/transform/remove_noop_landing_pads.rs
index 130393e2c4c..c636aba9fc6 100644
--- a/src/librustc_mir/transform/remove_noop_landing_pads.rs
+++ b/src/librustc_mir/transform/remove_noop_landing_pads.rs
@@ -9,7 +9,7 @@ use crate::util::patch::MirPatch;
 /// code for these.
 pub struct RemoveNoopLandingPads;
 
-pub fn remove_noop_landing_pads<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
+pub fn remove_noop_landing_pads<'tcx>(tcx: TyCtxt<'tcx>, body: &mut BodyCache<'tcx>) {
     if tcx.sess.no_landing_pads() {
         return
     }
@@ -19,7 +19,7 @@ pub fn remove_noop_landing_pads<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>)
 }
 
 impl<'tcx> MirPass<'tcx> for RemoveNoopLandingPads {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         remove_noop_landing_pads(tcx, body);
     }
 }
@@ -84,7 +84,7 @@ impl RemoveNoopLandingPads {
         }
     }
 
-    fn remove_nop_landing_pads(&self, body: &mut Body<'_>) {
+    fn remove_nop_landing_pads(&self, body: &mut BodyCache<'_>) {
         // make sure there's a single resume block
         let resume_block = {
             let patch = MirPatch::new(body);
diff --git a/src/librustc_mir/transform/rustc_peek.rs b/src/librustc_mir/transform/rustc_peek.rs
index aada7641df6..794ced1cb0e 100644
--- a/src/librustc_mir/transform/rustc_peek.rs
+++ b/src/librustc_mir/transform/rustc_peek.rs
@@ -5,7 +5,7 @@ use syntax_pos::Span;
 
 use rustc::ty::{self, TyCtxt, Ty};
 use rustc::hir::def_id::DefId;
-use rustc::mir::{self, Body, Location, Local};
+use rustc::mir::{self, Body, BodyCache, Location, Local};
 use rustc_index::bit_set::BitSet;
 use crate::transform::{MirPass, MirSource};
 
@@ -26,7 +26,7 @@ use crate::dataflow::has_rustc_mir_with;
 pub struct SanityCheck;
 
 impl<'tcx> MirPass<'tcx> for SanityCheck {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         let def_id = src.def_id();
         if !tcx.has_attr(def_id, sym::rustc_mir) {
             debug!("skipping rustc_peek::SanityCheck on {}", tcx.def_path_str(def_id));
@@ -64,10 +64,20 @@ impl<'tcx> MirPass<'tcx> for SanityCheck {
             sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_uninits);
         }
         if has_rustc_mir_with(&attributes, sym::rustc_peek_definite_init).is_some() {
-            sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_def_inits);
+            sanity_check_via_rustc_peek(
+                tcx,
+                body,
+                def_id,
+                &attributes,
+                &flow_def_inits);
         }
         if has_rustc_mir_with(&attributes, sym::rustc_peek_indirectly_mutable).is_some() {
-            sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_indirectly_mut);
+            sanity_check_via_rustc_peek(
+                tcx,
+                body,
+                def_id,
+                &attributes,
+                &flow_indirectly_mut);
         }
         if has_rustc_mir_with(&attributes, sym::stop_after_dataflow).is_some() {
             tcx.sess.fatal("stop_after_dataflow ended compilation");
diff --git a/src/librustc_mir/transform/simplify.rs b/src/librustc_mir/transform/simplify.rs
index c9185d14148..900752d3ce0 100644
--- a/src/librustc_mir/transform/simplify.rs
+++ b/src/librustc_mir/transform/simplify.rs
@@ -43,7 +43,7 @@ impl SimplifyCfg {
     }
 }
 
-pub fn simplify_cfg(body: &mut Body<'_>) {
+pub fn simplify_cfg(body: &mut BodyCache<'_>) {
     CfgSimplifier::new(body).simplify();
     remove_dead_blocks(body);
 
@@ -56,7 +56,9 @@ impl<'tcx> MirPass<'tcx> for SimplifyCfg {
         Cow::Borrowed(&self.label)
     }
 
-    fn run_pass(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body);
         simplify_cfg(body);
     }
@@ -68,7 +70,7 @@ pub struct CfgSimplifier<'a, 'tcx> {
 }
 
 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
-    pub fn new(body: &'a mut Body<'tcx>) -> Self {
+    pub fn new(body: &'a mut BodyCache<'tcx>) -> Self {
         let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks());
 
         // we can't use mir.predecessors() here because that counts
@@ -124,8 +126,9 @@ impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
                     changed |= inner_changed;
                 }
 
-                self.basic_blocks[bb].statements.extend(new_stmts);
-                self.basic_blocks[bb].terminator = Some(terminator);
+                let data = &mut self.basic_blocks[bb];
+                data.statements.extend(new_stmts);
+                data.terminator = Some(terminator);
 
                 changed |= inner_changed;
             }
@@ -259,7 +262,7 @@ impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
     }
 }
 
-pub fn remove_dead_blocks(body: &mut Body<'_>) {
+pub fn remove_dead_blocks(body: &mut BodyCache<'_>) {
     let mut seen = BitSet::new_empty(body.basic_blocks().len());
     for (bb, _) in traversal::preorder(body) {
         seen.insert(bb.index());
@@ -273,8 +276,8 @@ pub fn remove_dead_blocks(body: &mut Body<'_>) {
     for alive_index in seen.iter() {
         replacements[alive_index] = BasicBlock::new(used_blocks);
         if alive_index != used_blocks {
-            // Swap the next alive block data with the current available slot. Since alive_index is
-            // non-decreasing this is a valid operation.
+            // Swap the next alive block data with the current available slot. Since
+            // alive_index is non-decreasing this is a valid operation.
             basic_blocks.raw.swap(alive_index, used_blocks);
         }
         used_blocks += 1;
@@ -292,14 +295,17 @@ pub fn remove_dead_blocks(body: &mut Body<'_>) {
 pub struct SimplifyLocals;
 
 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(
+        &self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyCache<'tcx>
+    ) {
         trace!("running SimplifyLocals on {:?}", source);
         let locals = {
+            let read_only_cache = read_only!(body);
             let mut marker = DeclMarker {
                 locals: BitSet::new_empty(body.local_decls.len()),
                 body,
             };
-            marker.visit_body(body);
+            marker.visit_body(read_only_cache);
             // Return pointer and arguments are always live
             marker.locals.insert(RETURN_PLACE);
             for arg in body.args_iter() {
diff --git a/src/librustc_mir/transform/simplify_branches.rs b/src/librustc_mir/transform/simplify_branches.rs
index 0a509666d34..c8d0f37f9a5 100644
--- a/src/librustc_mir/transform/simplify_branches.rs
+++ b/src/librustc_mir/transform/simplify_branches.rs
@@ -19,7 +19,7 @@ impl<'tcx> MirPass<'tcx> for SimplifyBranches {
         Cow::Borrowed(&self.label)
     }
 
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         let param_env = tcx.param_env(src.def_id());
         for block in body.basic_blocks_mut() {
             let terminator = block.terminator_mut();
diff --git a/src/librustc_mir/transform/simplify_try.rs b/src/librustc_mir/transform/simplify_try.rs
index 9dc5daa9b07..2235de9a153 100644
--- a/src/librustc_mir/transform/simplify_try.rs
+++ b/src/librustc_mir/transform/simplify_try.rs
@@ -33,7 +33,7 @@ use itertools::Itertools as _;
 pub struct SimplifyArmIdentity;
 
 impl<'tcx> MirPass<'tcx> for SimplifyArmIdentity {
-    fn run_pass(&self, _: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, _: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         let (basic_blocks, local_decls) = body.basic_blocks_and_local_decls_mut();
         for bb in basic_blocks {
             // Need 3 statements:
@@ -151,7 +151,7 @@ fn match_variant_field_place<'tcx>(place: &Place<'tcx>) -> Option<(Local, VarFie
 pub struct SimplifyBranchSame;
 
 impl<'tcx> MirPass<'tcx> for SimplifyBranchSame {
-    fn run_pass(&self, _: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, _: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         let mut did_remove_blocks = false;
         let bbs = body.basic_blocks_mut();
         for bb_idx in bbs.indices() {
diff --git a/src/librustc_mir/transform/uniform_array_move_out.rs b/src/librustc_mir/transform/uniform_array_move_out.rs
index 28f68ac2de0..3fc76ef6b00 100644
--- a/src/librustc_mir/transform/uniform_array_move_out.rs
+++ b/src/librustc_mir/transform/uniform_array_move_out.rs
@@ -37,12 +37,14 @@ use crate::util::patch::MirPatch;
 pub struct UniformArrayMoveOut;
 
 impl<'tcx> MirPass<'tcx> for UniformArrayMoveOut {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         let mut patch = MirPatch::new(body);
         let param_env = tcx.param_env(src.def_id());
         {
-            let mut visitor = UniformArrayMoveOutVisitor{body, patch: &mut patch, tcx, param_env};
-            visitor.visit_body(body);
+            let read_only_cache = read_only!(body);
+            let mut visitor
+                = UniformArrayMoveOutVisitor{ body, patch: &mut patch, tcx, param_env};
+            visitor.visit_body(read_only_cache);
         }
         patch.apply(body);
     }
@@ -184,15 +186,16 @@ pub struct RestoreSubsliceArrayMoveOut<'tcx> {
 }
 
 impl<'tcx> MirPass<'tcx> for RestoreSubsliceArrayMoveOut<'tcx> {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         let mut patch = MirPatch::new(body);
         let param_env = tcx.param_env(src.def_id());
         {
+            let read_only_cache = read_only!(body);
             let mut visitor = RestoreDataCollector {
                 locals_use: IndexVec::from_elem(LocalUse::new(), &body.local_decls),
                 candidates: vec![],
             };
-            visitor.visit_body(body);
+            visitor.visit_body(read_only_cache);
 
             for candidate in &visitor.candidates {
                 let statement = &body[candidate.block].statements[candidate.statement_index];
@@ -217,8 +220,12 @@ impl<'tcx> MirPass<'tcx> for RestoreSubsliceArrayMoveOut<'tcx> {
 
                         let opt_src_place = items.first().and_then(|x| *x).map(|x| x.2);
                         let opt_size = opt_src_place.and_then(|src_place| {
-                            let src_ty =
-                                Place::ty_from(src_place.base, src_place.projection, body, tcx).ty;
+                            let src_ty = Place::ty_from(
+                                src_place.base,
+                                src_place.projection,
+                                &**body,
+                                tcx
+                            ).ty;
                             if let ty::Array(_, ref size_o) = src_ty.kind {
                                 size_o.try_eval_usize(tcx, param_env)
                             } else {
diff --git a/src/librustc_mir/transform/uninhabited_enum_branching.rs b/src/librustc_mir/transform/uninhabited_enum_branching.rs
index a6c18aee6a8..de070d75ad8 100644
--- a/src/librustc_mir/transform/uninhabited_enum_branching.rs
+++ b/src/librustc_mir/transform/uninhabited_enum_branching.rs
@@ -2,7 +2,8 @@
 
 use crate::transform::{MirPass, MirSource};
 use rustc::mir::{
-    BasicBlock, BasicBlockData, Body, Local, Operand, Rvalue, StatementKind, TerminatorKind,
+    BasicBlock, BasicBlockData, Body, BodyCache, Local, Operand, Rvalue, StatementKind,
+    TerminatorKind,
 };
 use rustc::ty::layout::{Abi, TyLayout, Variants};
 use rustc::ty::{Ty, TyCtxt};
@@ -65,7 +66,7 @@ fn variant_discriminants<'tcx>(
 }
 
 impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
-    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyCache<'tcx>) {
         if source.promoted.is_some() {
             return;
         }
diff --git a/src/librustc_mir/util/collect_writes.rs b/src/librustc_mir/util/collect_writes.rs
index c8804dfbaf2..f94bea20024 100644
--- a/src/librustc_mir/util/collect_writes.rs
+++ b/src/librustc_mir/util/collect_writes.rs
@@ -1,5 +1,5 @@
 use rustc::mir::{Local, Location};
-use rustc::mir::Body;
+use rustc::mir::ReadOnlyBodyCache;
 use rustc::mir::visit::PlaceContext;
 use rustc::mir::visit::Visitor;
 
@@ -9,10 +9,10 @@ crate trait FindAssignments {
     fn find_assignments(&self, local: Local) -> Vec<Location>;
 }
 
-impl<'tcx> FindAssignments for Body<'tcx>{
+impl<'a, 'tcx> FindAssignments for ReadOnlyBodyCache<'a, 'tcx>{
     fn find_assignments(&self, local: Local) -> Vec<Location>{
             let mut visitor = FindLocalAssignmentVisitor{ needle: local, locations: vec![]};
-            visitor.visit_body(self);
+            visitor.visit_body(*self);
             visitor.locations
     }
 }
diff --git a/src/librustc_mir/util/def_use.rs b/src/librustc_mir/util/def_use.rs
index 1611caddad1..1907e9bdc97 100644
--- a/src/librustc_mir/util/def_use.rs
+++ b/src/librustc_mir/util/def_use.rs
@@ -1,6 +1,6 @@
 //! Def-use analysis.
 
-use rustc::mir::{Body, Local, Location, PlaceElem, VarDebugInfo};
+use rustc::mir::{Body, BodyCache, Local, Location, PlaceElem, ReadOnlyBodyCache, VarDebugInfo};
 use rustc::mir::visit::{PlaceContext, MutVisitor, Visitor};
 use rustc::ty::TyCtxt;
 use rustc_index::vec::IndexVec;
@@ -30,7 +30,7 @@ impl DefUseAnalysis {
         }
     }
 
-    pub fn analyze(&mut self, body: &Body<'_>) {
+    pub fn analyze(&mut self, body: ReadOnlyBodyCache<'_, '_>) {
         self.clear();
 
         let mut finder = DefUseFinder {
@@ -55,11 +55,11 @@ impl DefUseAnalysis {
     fn mutate_defs_and_uses(
         &self,
         local: Local,
-        body: &mut Body<'tcx>,
+        body: &mut BodyCache<'tcx>,
         new_local: Local,
         tcx: TyCtxt<'tcx>,
     ) {
-        let mut visitor = MutateUseVisitor::new(local, new_local, body, tcx);
+        let mut visitor = MutateUseVisitor::new(local, new_local, tcx);
         let info = &self.info[local];
         for place_use in &info.defs_and_uses {
             visitor.visit_location(body, place_use.location)
@@ -73,7 +73,7 @@ impl DefUseAnalysis {
     // FIXME(pcwalton): this should update the def-use chains.
     pub fn replace_all_defs_and_uses_with(&self,
                                           local: Local,
-                                          body: &mut Body<'tcx>,
+                                          body: &mut BodyCache<'tcx>,
                                           new_local: Local,
                                           tcx: TyCtxt<'tcx>) {
         self.mutate_defs_and_uses(local, body, new_local, tcx)
@@ -156,7 +156,6 @@ impl MutateUseVisitor<'tcx> {
     fn new(
         query: Local,
         new_local: Local,
-        _: &Body<'tcx>,
         tcx: TyCtxt<'tcx>,
     ) -> MutateUseVisitor<'tcx> {
         MutateUseVisitor { query, new_local, tcx }
diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs
index 63e4af0a56a..334975373e5 100644
--- a/src/librustc_mir/util/liveness.rs
+++ b/src/librustc_mir/util/liveness.rs
@@ -57,7 +57,7 @@ pub struct LivenessResult {
 /// Computes which local variables are live within the given function
 /// `mir`, including drops.
 pub fn liveness_of_locals(
-    body: &Body<'_>,
+    body: ReadOnlyBodyCache<'_, '_>,
 ) -> LivenessResult {
     let num_live_vars = body.local_decls.len();
 
@@ -83,8 +83,9 @@ pub fn liveness_of_locals(
     // FIXME(ecstaticmorse): Reverse post-order on the reverse CFG may generate a better iteration
     // order when cycles are present, but the overhead of computing the reverse CFG may outweigh
     // any benefits. Benchmark this and find out.
-    let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks().len());
-    for (bb, _) in traversal::postorder(body) {
+    let mut dirty_queue: WorkQueue<BasicBlock>
+        = WorkQueue::with_none(body.basic_blocks().len());
+    for (bb, _) in traversal::postorder(&body) {
         dirty_queue.insert(bb);
     }
 
diff --git a/src/librustc_mir/util/patch.rs b/src/librustc_mir/util/patch.rs
index a5f7e540157..47bb0b699c0 100644
--- a/src/librustc_mir/util/patch.rs
+++ b/src/librustc_mir/util/patch.rs
@@ -127,7 +127,7 @@ impl<'tcx> MirPatch<'tcx> {
         self.make_nop.push(loc);
     }
 
-    pub fn apply(self, body: &mut Body<'tcx>) {
+    pub fn apply(self, body: &mut BodyCache<'tcx>) {
         debug!("MirPatch: make nops at: {:?}", self.make_nop);
         for loc in self.make_nop {
             body.make_statement_nop(loc);