Use a lock-free datastructure for `source_span`

10 files changed, 65 insertions, 12 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 6c17edd3020..93f8eda66bb 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1379,6 +1379,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "elsa"
+version = "1.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f74077c3c3aedb99a2683919698285596662518ea13e5eedcf8bdd43b0d0453b"
+dependencies = [
+ "stable_deref_trait",
+]
+
+[[package]]
 name = "ena"
 version = "0.14.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -3882,6 +3891,7 @@ dependencies = [
  "arrayvec 0.7.0",
  "bitflags",
  "cfg-if",
+ "elsa",
  "ena",
  "indexmap",
  "jobserver",
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml
index 0366fb0a148..a6601fbf43b 100644
--- a/compiler/rustc_data_structures/Cargo.toml
+++ b/compiler/rustc_data_structures/Cargo.toml
@@ -31,6 +31,7 @@ stacker = "0.1.15"
 tempfile = "3.2"
 thin-vec = "0.2.9"
 tracing = "0.1"
+elsa = "1.8"
 
 [dependencies.parking_lot]
 version = "0.11"
diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs
index ad71dcdf9d9..31323c21df0 100644
--- a/compiler/rustc_data_structures/src/sync.rs
+++ b/compiler/rustc_data_structures/src/sync.rs
@@ -26,6 +26,10 @@ use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe};
 pub use std::sync::atomic::Ordering;
 pub use std::sync::atomic::Ordering::SeqCst;
 
+pub use vec::AppendOnlyVec;
+
+mod vec;
+
 cfg_if! {
     if #[cfg(not(parallel_compiler))] {
         pub auto trait Send {}
diff --git a/compiler/rustc_data_structures/src/sync/vec.rs b/compiler/rustc_data_structures/src/sync/vec.rs
new file mode 100644
index 00000000000..cbea4f05999
--- /dev/null
+++ b/compiler/rustc_data_structures/src/sync/vec.rs
@@ -0,0 +1,41 @@
+use std::marker::PhantomData;
+
+use rustc_index::vec::Idx;
+
+pub struct AppendOnlyVec<I: Idx, T: Copy> {
+    #[cfg(not(parallel_compiler))]
+    vec: elsa::vec::FrozenVec<T>,
+    #[cfg(parallel_compiler)]
+    vec: elsa::sync::LockFreeFrozenVec<T>,
+    _marker: PhantomData<fn(&I)>,
+}
+
+impl<I: Idx, T: Copy> AppendOnlyVec<I, T> {
+    pub fn new() -> Self {
+        Self {
+            #[cfg(not(parallel_compiler))]
+            vec: elsa::vec::FrozenVec::new(),
+            #[cfg(parallel_compiler)]
+            vec: elsa::sync::LockFreeFrozenVec::new(),
+            _marker: PhantomData,
+        }
+    }
+
+    pub fn push(&self, val: T) -> I {
+        #[cfg(not(parallel_compiler))]
+        let i = self.vec.len();
+        #[cfg(not(parallel_compiler))]
+        self.vec.push(val);
+        #[cfg(parallel_compiler)]
+        let i = self.vec.push(val);
+        I::new(i)
+    }
+
+    pub fn get(&self, i: I) -> Option<T> {
+        let i = i.index();
+        #[cfg(not(parallel_compiler))]
+        return self.vec.get_copy(i);
+        #[cfg(parallel_compiler)]
+        return self.vec.get(i);
+    }
+}
diff --git a/compiler/rustc_interface/src/queries.rs b/compiler/rustc_interface/src/queries.rs
index c957578b59e..a96cc95a384 100644
--- a/compiler/rustc_interface/src/queries.rs
+++ b/compiler/rustc_interface/src/queries.rs
@@ -7,11 +7,10 @@ use rustc_codegen_ssa::traits::CodegenBackend;
 use rustc_codegen_ssa::CodegenResults;
 use rustc_data_structures::steal::Steal;
 use rustc_data_structures::svh::Svh;
-use rustc_data_structures::sync::{Lrc, OnceCell, RwLock, WorkerLocal};
+use rustc_data_structures::sync::{AppendOnlyVec, Lrc, OnceCell, RwLock, WorkerLocal};
 use rustc_hir::def_id::{CRATE_DEF_ID, LOCAL_CRATE};
 use rustc_hir::definitions::Definitions;
 use rustc_incremental::DepGraphFuture;
-use rustc_index::vec::IndexVec;
 use rustc_lint::LintStore;
 use rustc_metadata::creader::CStore;
 use rustc_middle::arena::Arena;
@@ -195,10 +194,9 @@ impl<'tcx> Queries<'tcx> {
 
             let cstore = RwLock::new(Box::new(CStore::new(sess)) as _);
             let definitions = RwLock::new(Definitions::new(sess.local_stable_crate_id()));
-            let mut source_span = IndexVec::default();
+            let source_span = AppendOnlyVec::new();
             let _id = source_span.push(krate.spans.inner_span);
             debug_assert_eq!(_id, CRATE_DEF_ID);
-            let source_span = RwLock::new(source_span);
             let untracked = Untracked { cstore, source_span, definitions };
 
             let qcx = passes::create_global_ctxt(
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index cf4836ded47..d95e4b56de0 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -1030,7 +1030,7 @@ impl<'tcx> TyCtxt<'tcx> {
     /// system if the result is otherwise tracked through queries
     #[inline]
     pub fn source_span_untracked(self, def_id: LocalDefId) -> Span {
-        self.untracked.source_span.read().get(def_id).copied().unwrap_or(DUMMY_SP)
+        self.untracked.source_span.get(def_id).unwrap_or(DUMMY_SP)
     }
 
     #[inline(always)]
@@ -2521,6 +2521,5 @@ pub fn provide(providers: &mut ty::query::Providers) {
         // We want to check if the panic handler was defined in this crate
         tcx.lang_items().panic_impl().map_or(false, |did| did.is_local())
     };
-    providers.source_span =
-        |tcx, def_id| tcx.untracked.source_span.read().get(def_id).copied().unwrap_or(DUMMY_SP);
+    providers.source_span = |tcx, def_id| tcx.untracked.source_span.get(def_id).unwrap_or(DUMMY_SP);
 }
diff --git a/compiler/rustc_query_system/src/ich/hcx.rs b/compiler/rustc_query_system/src/ich/hcx.rs
index 8db8ee9428b..5593a15412f 100644
--- a/compiler/rustc_query_system/src/ich/hcx.rs
+++ b/compiler/rustc_query_system/src/ich/hcx.rs
@@ -146,7 +146,7 @@ impl<'a> rustc_span::HashStableContext for StableHashingContext<'a> {
 
     #[inline]
     fn def_span(&self, def_id: LocalDefId) -> Span {
-        *self.untracked.source_span.read().get(def_id).unwrap_or(&DUMMY_SP)
+        self.untracked.source_span.get(def_id).unwrap_or(DUMMY_SP)
     }
 
     #[inline]
diff --git a/compiler/rustc_resolve/src/lib.rs b/compiler/rustc_resolve/src/lib.rs
index 66034baaa0b..9fd7edeb5a1 100644
--- a/compiler/rustc_resolve/src/lib.rs
+++ b/compiler/rustc_resolve/src/lib.rs
@@ -1156,7 +1156,7 @@ impl<'tcx> Resolver<'_, 'tcx> {
 
         // A relative span's parent must be an absolute span.
         debug_assert_eq!(span.data_untracked().parent, None);
-        let _id = self.tcx.untracked().source_span.write().push(span);
+        let _id = self.tcx.untracked().source_span.push(span);
         debug_assert_eq!(_id, def_id);
 
         // Some things for which we allocate `LocalDefId`s don't correspond to
diff --git a/compiler/rustc_session/src/cstore.rs b/compiler/rustc_session/src/cstore.rs
index ff13a0bbf3f..868ffdf0f1d 100644
--- a/compiler/rustc_session/src/cstore.rs
+++ b/compiler/rustc_session/src/cstore.rs
@@ -6,10 +6,9 @@ use crate::search_paths::PathKind;
 use crate::utils::NativeLibKind;
 use crate::Session;
 use rustc_ast as ast;
-use rustc_data_structures::sync::{self, MetadataRef, RwLock};
+use rustc_data_structures::sync::{self, AppendOnlyVec, MetadataRef, RwLock};
 use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, StableCrateId, LOCAL_CRATE};
 use rustc_hir::definitions::{DefKey, DefPath, DefPathHash, Definitions};
-use rustc_index::vec::IndexVec;
 use rustc_span::hygiene::{ExpnHash, ExpnId};
 use rustc_span::symbol::Symbol;
 use rustc_span::Span;
@@ -255,6 +254,6 @@ pub type CrateStoreDyn = dyn CrateStore + sync::Sync + sync::Send;
 pub struct Untracked {
     pub cstore: RwLock<Box<CrateStoreDyn>>,
     /// Reference span for definitions.
-    pub source_span: RwLock<IndexVec<LocalDefId, Span>>,
+    pub source_span: AppendOnlyVec<LocalDefId, Span>,
     pub definitions: RwLock<Definitions>,
 }
diff --git a/src/tools/tidy/src/deps.rs b/src/tools/tidy/src/deps.rs
index 4c93f8a16b6..bddfdcfaf19 100644
--- a/src/tools/tidy/src/deps.rs
+++ b/src/tools/tidy/src/deps.rs
@@ -120,6 +120,7 @@ const PERMITTED_RUSTC_DEPENDENCIES: &[&str] = &[
     "dissimilar",
     "dlmalloc",
     "either",
+    "elsa",
     "ena",
     "expect-test",
     "fallible-iterator", // dependency of `thorin`