Rollup merge of #71392 - ecstatic-morse:body-predecessor-cache-arc, r=nikomatsakis

Don't hold the predecessor cache lock longer than necessary

#71044 returns a `LockGuard` with the predecessor cache to callers of `Body::predecessors`. As a result, the lock around the predecessor cache could be held for an arbitrarily long time. This PR uses reference counting for ownership of the predecessor cache, meaning the lock is only ever held within `PredecessorCache::compute`. Checking this API for potential sources of deadlock is much easier now, since we no longer have to consider its consumers, only its internals.

This required removing `predecessors_for`, since there is no equivalent to `LockGuard::map` for `Arc` and `Rc`. I believe this could be emulated with `owning_ref::{Arc,Rc}Ref`, but I don't think it's necessary. Also, we continue to return an opaque type from `Body::predecessors` with the lifetime of the `Body`, not `'static`.

This depends on #71044. Only the last two commits are new.

r? @nikomatsakis

6 files changed, 35 insertions, 35 deletions

diff --git a/src/librustc_codegen_ssa/mir/mod.rs b/src/librustc_codegen_ssa/mir/mod.rs
index 1cd01c8c5bc..00b4bf96afa 100644
--- a/src/librustc_codegen_ssa/mir/mod.rs
+++ b/src/librustc_codegen_ssa/mir/mod.rs
@@ -157,7 +157,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     let cleanup_kinds = analyze::cleanup_kinds(&mir);
     // Allocate a `Block` for every basic block, except
     // the start block, if nothing loops back to it.
-    let reentrant_start_block = !mir.predecessors_for(mir::START_BLOCK).is_empty();
+    let reentrant_start_block = !mir.predecessors()[mir::START_BLOCK].is_empty();
     let block_bxs: IndexVec<mir::BasicBlock, Bx::BasicBlock> = mir
         .basic_blocks()
         .indices()
diff --git a/src/librustc_middle/mir/mod.rs b/src/librustc_middle/mir/mod.rs
index 341fec0c07b..34c05ec59f3 100644
--- a/src/librustc_middle/mir/mod.rs
+++ b/src/librustc_middle/mir/mod.rs
@@ -23,14 +23,12 @@ use rustc_ast::ast::Name;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::graph::dominators::{dominators, Dominators};
 use rustc_data_structures::graph::{self, GraphSuccessors};
-use rustc_data_structures::sync::MappedLockGuard;
 use rustc_index::bit_set::BitMatrix;
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_macros::HashStable;
 use rustc_serialize::{Decodable, Encodable};
 use rustc_span::symbol::Symbol;
 use rustc_span::{Span, DUMMY_SP};
-use smallvec::SmallVec;
 use std::borrow::Cow;
 use std::fmt::{self, Debug, Display, Formatter, Write};
 use std::ops::{Index, IndexMut};
@@ -170,7 +168,7 @@ pub struct Body<'tcx> {
     /// FIXME(oli-obk): rewrite the promoted during promotion to eliminate the cell components.
     pub ignore_interior_mut_in_const_validation: bool,
 
-    pub predecessor_cache: PredecessorCache,
+    predecessor_cache: PredecessorCache,
 }
 
 impl<'tcx> Body<'tcx> {
@@ -399,15 +397,6 @@ impl<'tcx> Body<'tcx> {
     }
 
     #[inline]
-    pub fn predecessors_for(
-        &self,
-        bb: BasicBlock,
-    ) -> impl std::ops::Deref<Target = SmallVec<[BasicBlock; 4]>> + '_ {
-        let predecessors = self.predecessor_cache.compute(&self.basic_blocks);
-        MappedLockGuard::map(predecessors, |preds| &mut preds[bb])
-    }
-
-    #[inline]
     pub fn predecessors(&self) -> impl std::ops::Deref<Target = Predecessors> + '_ {
         self.predecessor_cache.compute(&self.basic_blocks)
     }
@@ -2684,7 +2673,7 @@ impl graph::GraphPredecessors<'graph> for Body<'tcx> {
 impl graph::WithPredecessors for Body<'tcx> {
     #[inline]
     fn predecessors(&self, node: Self::Node) -> <Self as graph::GraphPredecessors<'_>>::Iter {
-        self.predecessors_for(node).clone().into_iter()
+        self.predecessors()[node].clone().into_iter()
     }
 }
 
diff --git a/src/librustc_middle/mir/predecessors.rs b/src/librustc_middle/mir/predecessors.rs
index 629b5c2efb7..9508365886a 100644
--- a/src/librustc_middle/mir/predecessors.rs
+++ b/src/librustc_middle/mir/predecessors.rs
@@ -1,5 +1,7 @@
+//! Lazily compute the reverse control-flow graph for the MIR.
+
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
-use rustc_data_structures::sync::{Lock, LockGuard, MappedLockGuard};
+use rustc_data_structures::sync::{Lock, Lrc};
 use rustc_index::vec::IndexVec;
 use rustc_serialize as serialize;
 use smallvec::SmallVec;
@@ -10,40 +12,49 @@ use crate::mir::{BasicBlock, BasicBlockData};
 pub type Predecessors = IndexVec<BasicBlock, SmallVec<[BasicBlock; 4]>>;
 
 #[derive(Clone, Debug)]
-pub struct PredecessorCache {
-    cache: Lock<Option<Predecessors>>,
+pub(super) struct PredecessorCache {
+    cache: Lock<Option<Lrc<Predecessors>>>,
 }
 
 impl PredecessorCache {
     #[inline]
-    pub fn new() -> Self {
+    pub(super) fn new() -> Self {
         PredecessorCache { cache: Lock::new(None) }
     }
 
+    /// Invalidates the predecessor cache.
+    ///
+    /// Invalidating the predecessor cache requires mutating the MIR, which in turn requires a
+    /// unique reference (`&mut`) to the `mir::Body`. Because of this, we can assume that all
+    /// callers of `invalidate` have a unique reference to the MIR and thus to the predecessor
+    /// cache. This means we don't actually need to take a lock when `invalidate` is called.
     #[inline]
-    pub fn invalidate(&mut self) {
+    pub(super) fn invalidate(&mut self) {
         *self.cache.get_mut() = None;
     }
 
+    /// Returns a ref-counted smart pointer containing the predecessor graph for this MIR.
+    ///
+    /// We use ref-counting instead of a mapped `LockGuard` here to ensure that the lock for
+    /// `cache` is only held inside this function. As long as no other locks are taken while
+    /// computing the predecessor graph, deadlock is impossible.
     #[inline]
-    pub fn compute(
+    pub(super) fn compute(
         &self,
         basic_blocks: &IndexVec<BasicBlock, BasicBlockData<'_>>,
-    ) -> MappedLockGuard<'_, Predecessors> {
-        LockGuard::map(self.cache.lock(), |cache| {
-            cache.get_or_insert_with(|| {
-                let mut preds = IndexVec::from_elem(SmallVec::new(), basic_blocks);
-                for (bb, data) in basic_blocks.iter_enumerated() {
-                    if let Some(term) = &data.terminator {
-                        for &succ in term.successors() {
-                            preds[succ].push(bb);
-                        }
+    ) -> Lrc<Predecessors> {
+        Lrc::clone(self.cache.lock().get_or_insert_with(|| {
+            let mut preds = IndexVec::from_elem(SmallVec::new(), basic_blocks);
+            for (bb, data) in basic_blocks.iter_enumerated() {
+                if let Some(term) = &data.terminator {
+                    for &succ in term.successors() {
+                        preds[succ].push(bb);
                     }
                 }
+            }
 
-                preds
-            })
-        })
+            Lrc::new(preds)
+        }))
     }
 }
 
diff --git a/src/librustc_mir/borrow_check/diagnostics/conflict_errors.rs b/src/librustc_mir/borrow_check/diagnostics/conflict_errors.rs
index 6cc4ee432a5..d424d0525fd 100644
--- a/src/librustc_mir/borrow_check/diagnostics/conflict_errors.rs
+++ b/src/librustc_mir/borrow_check/diagnostics/conflict_errors.rs
@@ -1269,7 +1269,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             location: Location,
         ) -> impl Iterator<Item = Location> + 'a {
             if location.statement_index == 0 {
-                let predecessors = body.predecessors_for(location.block).to_vec();
+                let predecessors = body.predecessors()[location.block].to_vec();
                 Either::Left(predecessors.into_iter().map(move |bb| body.terminator_loc(bb)))
             } else {
                 Either::Right(std::iter::once(Location {
diff --git a/src/librustc_mir/borrow_check/region_infer/values.rs b/src/librustc_mir/borrow_check/region_infer/values.rs
index 57a3fa6f79b..6cd814962c6 100644
--- a/src/librustc_mir/borrow_check/region_infer/values.rs
+++ b/src/librustc_mir/borrow_check/region_infer/values.rs
@@ -89,7 +89,7 @@ impl RegionValueElements {
             // If this is a basic block head, then the predecessors are
             // the terminators of other basic blocks
             stack.extend(
-                body.predecessors_for(block)
+                body.predecessors()[block]
                     .iter()
                     .map(|&pred_bb| body.terminator_loc(pred_bb))
                     .map(|pred_loc| self.point_from_location(pred_loc)),
diff --git a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
index af09dc5b803..ec52a08c7b2 100644
--- a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
+++ b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
@@ -303,7 +303,7 @@ impl LivenessResults<'me, 'typeck, 'flow, 'tcx> {
         }
 
         let body = self.cx.body;
-        for &pred_block in body.predecessors_for(block).iter() {
+        for &pred_block in body.predecessors()[block].iter() {
             debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,);
 
             // Check whether the variable is (at least partially)