Move predecessor cache outside of Body, use wrapper types to manage Cache and Body (WIP, amend this commit)

6 files changed, 300 insertions, 161 deletions

diff --git a/src/librustc/mir/cache.rs b/src/librustc/mir/cache.rs
index 8dac356c0a2..4300a5acba4 100644
--- a/src/librustc/mir/cache.rs
+++ b/src/librustc/mir/cache.rs
@@ -1,47 +1,255 @@
 use rustc_index::vec::IndexVec;
-use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
-use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
-use crate::ich::StableHashingContext;
-use crate::mir::BasicBlock;
+//use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+//use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
+//use crate::ich::StableHashingContext;
+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::{Index, IndexMut};
+use std::vec::IntoIter;
 
 #[derive(Clone, Debug)]
-pub(in crate::mir) struct Cache {
-    pub(in crate::mir) predecessors: Option<IndexVec<BasicBlock, Vec<BasicBlock>>>
+pub struct Cache {
+    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)
+//impl<'tcx, T> rustc_serialize::Encodable for Cache<'tcx, T> {
+//    fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
+//        Encodable::encode(&(), s)
+//    }
+//}
+//
+//impl<'tcx, T> rustc_serialize::Decodable for Cache<'tcx, T> {
+//    fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
+//        Decodable::decode(d).map(|_v: ()| Self::new())
+//    }
+//}
+//
+//impl<'a, 'tcx, T> HashStable<StableHashingContext<'a>> for Cache<'tcx, T> {
+//    fn hash_stable(&self, _: &mut StableHashingContext<'a>, _: &mut StableHasher) {
+//        // Do nothing.
+//    }
+//}
+
+impl Cache {
+    pub fn new() -> Self {
+        Self {
+            predecessors: None,
+        }
+    }
+
+    #[inline]
+    pub fn invalidate_predecessors(&mut self) {
+        // FIXME: consider being more fine-grained
+        self.predecessors = None;
+    }
+
+    #[inline]
+    /// This will recompute the predecessors cache if it is not available
+    pub fn predecessors(&mut self, body: &Body<'_>) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
+        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)
+        }
+
+        self.predecessors.as_ref().unwrap()
+    }
+
+    #[inline]
+    pub fn predecessors_for(&mut self, bb: BasicBlock, body: &Body<'_>) -> &[BasicBlock] {
+        &self.predecessors(body)[bb]
+    }
+
+    #[inline]
+    pub fn predecessor_locations<'a>(&'a mut 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.predecessors_for(loc.block, body);
+            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)
+    }
+
+    #[inline]
+    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
+    }
+
+    #[inline]
+    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)
+    }
+}
+
+pub struct OwningCache<'tcx> {
+    cache: Cache,
+    body: Body<'tcx>,
+}
+
+impl<'tcx> OwningCache<'tcx> {
+    pub fn borrow(&mut self) -> BorrowedCache<'_, 'tcx> {
+        BorrowedCache {
+            cache: &mut self.cache,
+            body: &self.body,
+        }
+    }
+
+    pub fn borrow_mut(&mut self) -> MutCache<'_, 'tcx> {
+        MutCache {
+            cache: &mut self.cache,
+            body: &mut self.body,
+        }
+    }
+}
+
+pub struct BorrowedCache<'a, 'tcx> {
+    cache: &'a mut Cache,
+    body: &'a Body<'tcx>
+}
+
+impl<'a, 'tcx> BorrowedCache<'a, 'tcx> {
+    #[inline]
+    pub fn predecessors_for(&mut self, bb: BasicBlock) -> &[BasicBlock] {
+        self.cache.predecessors_for(bb, self.body)
+    }
+
+    #[inline]
+    pub fn body(&self) -> &Body<'tcx> {
+        self.body
+    }
+
+    #[inline]
+    pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
+        &self.body.basic_blocks
+    }
+
+    #[inline]
+    pub fn dominators(&mut self) -> Dominators<BasicBlock> {
+        dominators(self)
     }
 }
 
-impl rustc_serialize::Decodable for Cache {
-    fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
-        Decodable::decode(d).map(|_v: ()| Self::new())
+impl<'a, 'tcx> Index<BasicBlock> for BorrowedCache<'a, 'tcx> {
+    type Output = BasicBlockData<'tcx>;
+
+    #[inline]
+    fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
+        &self.body[index]
     }
 }
 
-impl<'a> HashStable<StableHashingContext<'a>> for Cache {
-    fn hash_stable(&self, _: &mut StableHashingContext<'a>, _: &mut StableHasher) {
-        // Do nothing.
+impl<'a, 'tcx> graph::DirectedGraph for BorrowedCache<'a, 'tcx> {
+    type Node = BasicBlock;
+}
+
+impl<'a, 'graph, 'tcx> graph::GraphPredecessors<'graph> for BorrowedCache<'a, 'tcx> {
+    type Item = BasicBlock;
+    type Iter = IntoIter<BasicBlock>;
+}
+
+impl<'a, 'tcx> graph::WithPredecessors for BorrowedCache<'a, 'tcx> {
+    fn predecessors(
+        &mut self,
+        node: Self::Node,
+    ) -> <Self as GraphPredecessors<'_>>::Iter {
+        self.predecessors_for(node).to_vec().into_iter()
     }
 }
 
-impl Cache {
-    pub fn new() -> Self {
-        Cache {
-            predecessors: None
-        }
+impl<'a, 'tcx> graph::WithNumNodes for BorrowedCache<'a, 'tcx> {
+    fn num_nodes(&self) -> usize {
+        self.body.num_nodes()
     }
+}
 
+impl<'a, 'tcx> graph::WithStartNode for BorrowedCache<'a, 'tcx> {
+    fn start_node(&self) -> Self::Node {
+        self.body.start_node()
+    }
+}
+
+impl<'a, 'tcx> graph::WithSuccessors for BorrowedCache<'a, 'tcx> {
+    fn successors(
+        &self,
+        node: Self::Node,
+    ) -> <Self as GraphSuccessors<'_>>::Iter {
+        self.body.successors(node)
+    }
+}
+
+impl<'a, 'b, 'tcx> graph::GraphSuccessors<'b> for BorrowedCache<'a, 'tcx> {
+    type Item = BasicBlock;
+    type Iter = iter::Cloned<Successors<'b>>;
+}
+
+pub struct MutCache<'a, 'tcx> {
+    cache: &'a mut Cache,
+    body: &'a mut Body<'tcx>,
+}
+
+impl<'a, 'tcx> MutCache<'a, 'tcx> {
     #[inline]
-    pub fn invalidate_predecessors(&mut self) {
-        // FIXME: consider being more fine-grained
-        self.predecessors = None;
+    pub fn body(&mut self) -> &mut Body<'tcx> {
+        self.body
+    }
+
+    #[inline]
+    pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
+        &self.body.basic_blocks
+    }
+
+    #[inline]
+    pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
+        self.cache.basic_blocks_mut(&mut self.body)
     }
 }
 
-CloneTypeFoldableAndLiftImpls! {
-    Cache,
+impl<'a, 'tcx> Index<BasicBlock> for MutCache<'a, 'tcx> {
+    type Output = BasicBlockData<'tcx>;
+
+    #[inline]
+    fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
+        &self.body[index]
+    }
 }
+
+impl<'a, 'tcx> IndexMut<BasicBlock> for MutCache<'a, 'tcx> {
+    fn index_mut(&mut self, index: BasicBlock) -> &mut Self::Output {
+        self.cache.invalidate_predecessors();
+        &mut self.body.basic_blocks[index]
+    }
+}
+
+//CloneTypeFoldableAndLiftImpls! {
+//    Cache,
+//}
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index fb5ee211de2..fa435b9a51b 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -21,8 +21,8 @@ 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_macros::HashStable;
@@ -30,9 +30,8 @@ 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;
@@ -40,7 +39,7 @@ use syntax_pos::{Span, DUMMY_SP};
 
 pub use crate::mir::interpret::AssertMessage;
 
-mod cache;
+pub mod cache;
 pub mod interpret;
 pub mod mono;
 pub mod tcx;
@@ -153,9 +152,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> {
@@ -192,7 +188,6 @@ impl<'tcx> Body<'tcx> {
             spread_arg: None,
             var_debug_info,
             span,
-            cache: cache::Cache::new(),
             control_flow_destroyed,
         }
     }
@@ -202,88 +197,6 @@ impl<'tcx> Body<'tcx> {
         &self.basic_blocks
     }
 
-    #[inline]
-    pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
-        debug!("bbm: Clearing predecessors cache for body at: {:?}", self.span.data());
-        self.cache.invalidate_predecessors();
-        &mut self.basic_blocks
-    }
-
-    #[inline]
-    pub fn basic_blocks_and_local_decls_mut(
-        &mut self,
-    ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
-        debug!("bbaldm: Clearing predecessors cache for body at: {:?}", self.span.data());
-        self.cache.invalidate_predecessors();
-        (&mut self.basic_blocks, &mut self.local_decls)
-    }
-
-    #[inline]
-    pub fn unwrap_predecessors(&self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
-        assert!(
-            self.cache.predecessors.is_some(),
-            "Expected cache.predecessors to be `Some(...)` for block at: {:?}",
-            self.span.data()
-        );
-        self.cache.predecessors.as_ref().unwrap()
-    }
-
-    #[inline]
-    pub fn ensure_predecessors(&mut self) {
-        if self.cache.predecessors.is_none() {
-            let mut result = IndexVec::from_elem(vec![], self.basic_blocks());
-            for (bb, data) in self.basic_blocks().iter_enumerated() {
-                if let Some(ref term) = data.terminator {
-                    for &tgt in term.successors() {
-                        result[tgt].push(bb);
-                    }
-                }
-            }
-
-            self.cache.predecessors = Some(result)
-        }
-    }
-
-    #[inline]
-    /// This will recompute the predecessors cache if it is not available
-    pub fn predecessors(&mut self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
-        self.ensure_predecessors();
-        self.cache.predecessors.as_ref().unwrap()
-    }
-
-    #[inline]
-    pub fn predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
-        &self.unwrap_predecessors()[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 {
@@ -384,7 +297,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()
     }
@@ -444,13 +357,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,
@@ -2647,15 +2553,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).to_vec().into_iter()
-    }
-}
-
 impl<'tcx> graph::WithSuccessors for Body<'tcx> {
     fn successors(
         &self,
@@ -2665,11 +2562,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>>;
@@ -2704,7 +2596,7 @@ 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, mut body_cache: cache::BorrowedCache<'_, '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 {
@@ -2712,13 +2604,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).to_vec();
+        let mut queue: Vec<BasicBlock> = body_cache.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.extend(body.predecessors_for(block).iter().cloned());
+                queue.extend(body_cache.predecessors_for(block).iter().cloned());
             } else {
                 continue;
             }
diff --git a/src/librustc/mir/visit.rs b/src/librustc/mir/visit.rs
index 145593f1c4d..fbcfe104839 100644
--- a/src/librustc/mir/visit.rs
+++ b/src/librustc/mir/visit.rs
@@ -1,6 +1,7 @@
 use crate::ty::subst::SubstsRef;
 use crate::ty::{CanonicalUserTypeAnnotation, Ty};
 use crate::mir::*;
+use crate::mir::cache::*;
 use syntax_pos::Span;
 
 // # The MIR Visitor
@@ -71,8 +72,8 @@ macro_rules! make_mir_visitor {
             // Override these, and call `self.super_xxx` to revert back to the
             // default behavior.
 
-            fn visit_body(&mut self, body: & $($mutability)? Body<'tcx>) {
-                self.super_body(body);
+            fn visit_body(&mut self, body_cache: & $($mutability)? cache_type!('tcx $($mutability)?)) {
+                self.super_body(body_cache);
             }
 
             fn visit_basic_block_data(&mut self,
@@ -241,10 +242,11 @@ macro_rules! make_mir_visitor {
             // not meant to be overridden.
 
             fn super_body(&mut self,
-                         body: & $($mutability)? Body<'tcx>) {
-                if let Some(yield_ty) = &$($mutability)? body.yield_ty {
+                         body_cache: & $($mutability)? cache_type!('tcx $($mutability)?)) {
+                let span = body_cache.body().span;
+                if let Some(yield_ty) = &$($mutability)? body_cache.body().yield_ty {
                     self.visit_ty(yield_ty, TyContext::YieldTy(SourceInfo {
-                        span: body.span,
+                        span,
                         scope: OUTERMOST_SOURCE_SCOPE,
                     }));
                 }
@@ -253,13 +255,14 @@ macro_rules! make_mir_visitor {
                 // than a for-loop, to avoid calling `body::Body::invalidate` for
                 // each basic block.
                 macro_rules! basic_blocks {
-                    (mut) => (body.basic_blocks_mut().iter_enumerated_mut());
-                    () => (body.basic_blocks().iter_enumerated());
+                    (mut) => (body_cache.basic_blocks_mut().iter_enumerated_mut());
+                    () => (body_cache.basic_blocks().iter_enumerated());
                 };
                 for (bb, data) in basic_blocks!($($mutability)?) {
                     self.visit_basic_block_data(bb, data);
                 }
 
+                let body = body_cache.body();
                 for scope in &$($mutability)? body.source_scopes {
                     self.visit_source_scope_data(scope);
                 }
@@ -790,8 +793,8 @@ macro_rules! make_mir_visitor {
 
             // Convenience methods
 
-            fn visit_location(&mut self, body: & $($mutability)? Body<'tcx>, location: Location) {
-                let basic_block = & $($mutability)? body[location.block];
+            fn visit_location(&mut self, body_cache: & $($mutability)? cache_type!('tcx $($mutability)?), location: Location) {
+                let basic_block = & $($mutability)? body_cache[location.block];
                 if basic_block.statements.len() == location.statement_index {
                     if let Some(ref $($mutability)? terminator) = basic_block.terminator {
                         self.visit_terminator(terminator, location)
@@ -806,6 +809,11 @@ macro_rules! make_mir_visitor {
     }
 }
 
+macro_rules! cache_type {
+    ($tcx:lifetime mut) => {MutCache<'_, $tcx>};
+    ($tcx:lifetime) => {BorrowedCache<'_, $tcx>};
+}
+
 macro_rules! visit_place_fns {
     (mut) => (
         fn tcx<'a>(&'a self) -> TyCtxt<'tcx>;
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_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index 37335799d19..9ce60d207ad 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -50,7 +50,7 @@ where
     Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
 {
     fn predecessors(
-        &self,
+        &mut self,
         node: Self::Node,
     ) -> <Self as GraphPredecessors<'_>>::Iter;
 }
diff --git a/src/librustc_data_structures/graph/reference.rs b/src/librustc_data_structures/graph/reference.rs
index 9442bb3cdec..bc4458334d5 100644
--- a/src/librustc_data_structures/graph/reference.rs
+++ b/src/librustc_data_structures/graph/reference.rs
@@ -4,11 +4,20 @@ impl<'graph, G: DirectedGraph> DirectedGraph for &'graph G {
     type Node = G::Node;
 }
 
+impl<'graph, G: DirectedGraph> DirectedGraph for &'graph mut G {
+    type Node = G::Node;
+}
+
 impl<'graph, G: WithNumNodes> WithNumNodes for &'graph G {
     fn num_nodes(&self) -> usize {
         (**self).num_nodes()
     }
 }
+impl<'graph, G: WithNumNodes> WithNumNodes for &'graph mut G {
+    fn num_nodes(&self) -> usize {
+        (**self).num_nodes()
+    }
+}
 
 impl<'graph, G: WithStartNode> WithStartNode for &'graph G {
     fn start_node(&self) -> Self::Node {
@@ -16,14 +25,25 @@ impl<'graph, G: WithStartNode> WithStartNode for &'graph G {
     }
 }
 
+impl<'graph, G: WithStartNode> WithStartNode for &'graph mut G {
+    fn start_node(&self) -> Self::Node {
+        (**self).start_node()
+    }
+}
+
 impl<'graph, G: WithSuccessors> WithSuccessors for &'graph G {
     fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter {
         (**self).successors(node)
     }
 }
+impl<'graph, G: WithSuccessors> WithSuccessors for &'graph mut G {
+    fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter {
+        (**self).successors(node)
+    }
+}
 
-impl<'graph, G: WithPredecessors> WithPredecessors for &'graph G {
-    fn predecessors(&self,
+impl<'graph, G: WithPredecessors> WithPredecessors for &'graph mut G {
+    fn predecessors(&mut self,
                     node: Self::Node)
                     -> <Self as GraphPredecessors<'_>>::Iter {
         (**self).predecessors(node)
@@ -35,7 +55,17 @@ impl<'iter, 'graph, G: WithPredecessors> GraphPredecessors<'iter> for &'graph G
     type Iter = <G as GraphPredecessors<'iter>>::Iter;
 }
 
+impl<'iter, 'graph, G: WithPredecessors> GraphPredecessors<'iter> for &'graph mut G {
+    type Item = G::Node;
+    type Iter = <G as GraphPredecessors<'iter>>::Iter;
+}
+
 impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph G {
     type Item = G::Node;
     type Iter = <G as GraphSuccessors<'iter>>::Iter;
 }
+
+impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph mut G {
+    type Item = G::Node;
+    type Iter = <G as GraphSuccessors<'iter>>::Iter;
+}