summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_data_structures
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--compiler/rustc_data_structures/Cargo.toml5
-rw-r--r--compiler/rustc_data_structures/src/functor.rs51
-rw-r--r--compiler/rustc_data_structures/src/graph/dominators/mod.rs51
-rw-r--r--compiler/rustc_data_structures/src/graph/scc/mod.rs18
-rw-r--r--compiler/rustc_data_structures/src/lib.rs2
-rw-r--r--compiler/rustc_data_structures/src/obligation_forest/mod.rs10
-rw-r--r--compiler/rustc_data_structures/src/profiling.rs50
-rw-r--r--compiler/rustc_data_structures/src/sorted_map/index_map.rs5
-rw-r--r--compiler/rustc_data_structures/src/sorted_map/tests.rs4
-rw-r--r--compiler/rustc_data_structures/src/stable_hasher.rs8
-rw-r--r--compiler/rustc_data_structures/src/stable_hasher/tests.rs2
-rw-r--r--compiler/rustc_data_structures/src/sync.rs8
-rw-r--r--compiler/rustc_data_structures/src/sync/vec.rs41
13 files changed, 215 insertions, 40 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml
index 0366fb0a1..29cb2c0a3 100644
--- a/compiler/rustc_data_structures/Cargo.toml
+++ b/compiler/rustc_data_structures/Cargo.toml
@@ -9,7 +9,7 @@ edition = "2021"
arrayvec = { version = "0.7", default-features = false }
bitflags = "1.2.1"
cfg-if = "1.0"
-ena = "0.14"
+ena = "0.14.1"
indexmap = { version = "1.9.1" }
jobserver_crate = { version = "0.1.13", package = "jobserver" }
libc = "0.2"
@@ -29,8 +29,9 @@ smallvec = { version = "1.8.1", features = [
stable_deref_trait = "1.0.0"
stacker = "0.1.15"
tempfile = "3.2"
-thin-vec = "0.2.9"
+thin-vec = "0.2.12"
tracing = "0.1"
+elsa = "1.8"
[dependencies.parking_lot]
version = "0.11"
diff --git a/compiler/rustc_data_structures/src/functor.rs b/compiler/rustc_data_structures/src/functor.rs
index 84cb417dd..28fcf80b3 100644
--- a/compiler/rustc_data_structures/src/functor.rs
+++ b/compiler/rustc_data_structures/src/functor.rs
@@ -1,5 +1,5 @@
use rustc_index::vec::{Idx, IndexVec};
-use std::mem;
+use std::{mem, rc::Rc, sync::Arc};
pub trait IdFunctor: Sized {
type Inner;
@@ -65,3 +65,52 @@ impl<I: Idx, T> IdFunctor for IndexVec<I, T> {
self.raw.try_map_id(f).map(IndexVec::from_raw)
}
}
+
+macro_rules! rc {
+ ($($rc:ident),+) => {$(
+ impl<T: Clone> IdFunctor for $rc<T> {
+ type Inner = T;
+
+ #[inline]
+ fn try_map_id<F, E>(mut self, mut f: F) -> Result<Self, E>
+ where
+ F: FnMut(Self::Inner) -> Result<Self::Inner, E>,
+ {
+ // We merely want to replace the contained `T`, if at all possible,
+ // so that we don't needlessly allocate a new `$rc` or indeed clone
+ // the contained type.
+ unsafe {
+ // First step is to ensure that we have a unique reference to
+ // the contained type, which `$rc::make_mut` will accomplish (by
+ // allocating a new `$rc` and cloning the `T` only if required).
+ // This is done *before* casting to `$rc<ManuallyDrop<T>>` so that
+ // panicking during `make_mut` does not leak the `T`.
+ $rc::make_mut(&mut self);
+
+ // Casting to `$rc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
+ // is `repr(transparent)`.
+ let ptr = $rc::into_raw(self).cast::<mem::ManuallyDrop<T>>();
+ let mut unique = $rc::from_raw(ptr);
+
+ // Call to `$rc::make_mut` above guarantees that `unique` is the
+ // sole reference to the contained value, so we can avoid doing
+ // a checked `get_mut` here.
+ let slot = $rc::get_mut_unchecked(&mut unique);
+
+ // Semantically move the contained type out from `unique`, fold
+ // it, then move the folded value back into `unique`. Should
+ // folding fail, `ManuallyDrop` ensures that the "moved-out"
+ // value is not re-dropped.
+ let owned = mem::ManuallyDrop::take(slot);
+ let folded = f(owned)?;
+ *slot = mem::ManuallyDrop::new(folded);
+
+ // Cast back to `$rc<T>`.
+ Ok($rc::from_raw($rc::into_raw(unique).cast()))
+ }
+ }
+ }
+ )+};
+}
+
+rc! { Rc, Arc }
diff --git a/compiler/rustc_data_structures/src/graph/dominators/mod.rs b/compiler/rustc_data_structures/src/graph/dominators/mod.rs
index 471457f61..0a21a4249 100644
--- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs
@@ -135,7 +135,47 @@ pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> {
// This loop computes the semi[w] for w.
semi[w] = w;
for v in graph.predecessors(pre_order_to_real[w]) {
- // Reachable vertices may have unreachable predecessors, so ignore any of them
+ // TL;DR: Reachable vertices may have unreachable predecessors, so ignore any of them.
+ //
+ // Ignore blocks which are not connected to the entry block.
+ //
+ // The algorithm that was used to traverse the graph and build the
+ // `pre_order_to_real` and `real_to_pre_order` vectors does so by
+ // starting from the entry block and following the successors.
+ // Therefore, any blocks not reachable from the entry block will be
+ // set to `None` in the `pre_order_to_real` vector.
+ //
+ // For example, in this graph, A and B should be skipped:
+ //
+ // ┌─────┐
+ // │ │
+ // └──┬──┘
+ // │
+ // ┌──▼──┐ ┌─────┐
+ // │ │ │ A │
+ // └──┬──┘ └──┬──┘
+ // │ │
+ // ┌───────┴───────┐ │
+ // │ │ │
+ // ┌──▼──┐ ┌──▼──┐ ┌──▼──┐
+ // │ │ │ │ │ B │
+ // └──┬──┘ └──┬──┘ └──┬──┘
+ // │ └──────┬─────┘
+ // ┌──▼──┐ │
+ // │ │ │
+ // └──┬──┘ ┌──▼──┐
+ // │ │ │
+ // │ └─────┘
+ // ┌──▼──┐
+ // │ │
+ // └──┬──┘
+ // │
+ // ┌──▼──┐
+ // │ │
+ // └─────┘
+ //
+ // ...this may be the case if a MirPass modifies the CFG to remove
+ // or rearrange certain blocks/edges.
let Some(v) = real_to_pre_order[v] else {
continue
};
@@ -264,13 +304,18 @@ fn compress(
}
}
+/// Tracks the list of dominators for each node.
#[derive(Clone, Debug)]
pub struct Dominators<N: Idx> {
post_order_rank: IndexVec<N, usize>,
+ // Even though we track only the immediate dominator of each node, it's
+ // possible to get its full list of dominators by looking up the dominator
+ // of each dominator. (See the `impl Iterator for Iter` definition).
immediate_dominators: IndexVec<N, Option<N>>,
}
impl<Node: Idx> Dominators<Node> {
+ /// Whether the given Node has an immediate dominator.
pub fn is_reachable(&self, node: Node) -> bool {
self.immediate_dominators[node].is_some()
}
@@ -280,12 +325,14 @@ impl<Node: Idx> Dominators<Node> {
self.immediate_dominators[node].unwrap()
}
+ /// Provides an iterator over each dominator up the CFG, for the given Node.
+ /// See the `impl Iterator for Iter` definition to understand how this works.
pub fn dominators(&self, node: Node) -> Iter<'_, Node> {
assert!(self.is_reachable(node), "node {node:?} is not reachable");
Iter { dominators: self, node: Some(node) }
}
- pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
+ pub fn dominates(&self, dom: Node, node: Node) -> bool {
// FIXME -- could be optimized by using post-order-rank
self.dominators(node).any(|n| n == dom)
}
diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs
index c8e66eb67..c4b11951a 100644
--- a/compiler/rustc_data_structures/src/graph/scc/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs
@@ -27,7 +27,7 @@ pub struct Sccs<N: Idx, S: Idx> {
scc_data: SccData<S>,
}
-struct SccData<S: Idx> {
+pub struct SccData<S: Idx> {
/// For each SCC, the range of `all_successors` where its
/// successors can be found.
ranges: IndexVec<S, Range<usize>>,
@@ -43,6 +43,14 @@ impl<N: Idx, S: Idx + Ord> Sccs<N, S> {
SccsConstruction::construct(graph)
}
+ pub fn scc_indices(&self) -> &IndexVec<N, S> {
+ &self.scc_indices
+ }
+
+ pub fn scc_data(&self) -> &SccData<S> {
+ &self.scc_data
+ }
+
/// Returns the number of SCCs in the graph.
pub fn num_sccs(&self) -> usize {
self.scc_data.len()
@@ -115,6 +123,14 @@ impl<S: Idx> SccData<S> {
self.ranges.len()
}
+ pub fn ranges(&self) -> &IndexVec<S, Range<usize>> {
+ &self.ranges
+ }
+
+ pub fn all_successors(&self) -> &Vec<S> {
+ &self.all_successors
+ }
+
/// Returns the successors of the given SCC.
fn successors(&self, scc: S) -> &[S] {
// Annoyingly, `range` does not implement `Copy`, so we have
diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 954e84c30..a94e52fdf 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -11,6 +11,7 @@
#![feature(associated_type_bounds)]
#![feature(auto_traits)]
#![feature(cell_leak)]
+#![feature(core_intrinsics)]
#![feature(extend_one)]
#![feature(hash_raw_entry)]
#![feature(hasher_prefixfree_extras)]
@@ -25,6 +26,7 @@
#![feature(test)]
#![feature(thread_id_value)]
#![feature(vec_into_raw_parts)]
+#![feature(get_mut_unchecked)]
#![allow(rustc::default_hash_types)]
#![allow(rustc::potential_query_instability)]
#![deny(rustc::untranslatable_diagnostic)]
diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
index 10e673cd9..91abdaada 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
@@ -95,10 +95,7 @@ pub trait ForestObligation: Clone + Debug {
pub trait ObligationProcessor {
type Obligation: ForestObligation;
type Error: Debug;
- type OUT: OutcomeTrait<
- Obligation = Self::Obligation,
- Error = Error<Self::Obligation, Self::Error>,
- >;
+ type OUT: OutcomeTrait<Obligation = Self::Obligation, Error = Error<Self::Obligation, Self::Error>>;
fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool;
@@ -139,8 +136,7 @@ pub enum ProcessResult<O, E> {
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
struct ObligationTreeId(usize);
-type ObligationTreeIdGenerator =
- std::iter::Map<std::ops::RangeFrom<usize>, fn(usize) -> ObligationTreeId>;
+type ObligationTreeIdGenerator = impl Iterator<Item = ObligationTreeId>;
pub struct ObligationForest<O: ForestObligation> {
/// The list of obligations. In between calls to [Self::process_obligations],
@@ -430,6 +426,7 @@ impl<O: ForestObligation> ObligationForest<O> {
// nodes. Therefore we use a `while` loop.
let mut index = 0;
while let Some(node) = self.nodes.get_mut(index) {
+ // This test is extremely hot.
if node.state.get() != NodeState::Pending
|| !processor.needs_process_obligation(&node.obligation)
{
@@ -443,6 +440,7 @@ impl<O: ForestObligation> ObligationForest<O> {
// out of sync with `nodes`. It's not very common, but it does
// happen, and code in `compress` has to allow for it.
+ // This code is much less hot.
match processor.process_obligation(&mut node.obligation) {
ProcessResult::Unchanged => {
// No change in state.
diff --git a/compiler/rustc_data_structures/src/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs
index 393f17390..443316836 100644
--- a/compiler/rustc_data_structures/src/profiling.rs
+++ b/compiler/rustc_data_structures/src/profiling.rs
@@ -88,6 +88,7 @@ use std::borrow::Borrow;
use std::collections::hash_map::Entry;
use std::error::Error;
use std::fs;
+use std::intrinsics::unlikely;
use std::path::Path;
use std::process;
use std::sync::Arc;
@@ -206,8 +207,7 @@ impl SelfProfilerRef {
/// a measureme event, "verbose" generic activities also print a timing entry to
/// stderr if the compiler is invoked with -Ztime-passes.
pub fn verbose_generic_activity(&self, event_label: &'static str) -> VerboseTimingGuard<'_> {
- let message =
- if self.print_verbose_generic_activities { Some(event_label.to_owned()) } else { None };
+ let message = self.print_verbose_generic_activities.then(|| event_label.to_owned());
VerboseTimingGuard::start(message, self.generic_activity(event_label))
}
@@ -221,11 +221,9 @@ impl SelfProfilerRef {
where
A: Borrow<str> + Into<String>,
{
- let message = if self.print_verbose_generic_activities {
- Some(format!("{}({})", event_label, event_arg.borrow()))
- } else {
- None
- };
+ let message = self
+ .print_verbose_generic_activities
+ .then(|| format!("{}({})", event_label, event_arg.borrow()));
VerboseTimingGuard::start(message, self.generic_activity_with_arg(event_label, event_arg))
}
@@ -395,11 +393,18 @@ impl SelfProfilerRef {
/// Record a query in-memory cache hit.
#[inline(always)]
pub fn query_cache_hit(&self, query_invocation_id: QueryInvocationId) {
- self.instant_query_event(
- |profiler| profiler.query_cache_hit_event_kind,
- query_invocation_id,
- EventFilter::QUERY_CACHE_HITS,
- );
+ #[inline(never)]
+ #[cold]
+ fn cold_call(profiler_ref: &SelfProfilerRef, query_invocation_id: QueryInvocationId) {
+ profiler_ref.instant_query_event(
+ |profiler| profiler.query_cache_hit_event_kind,
+ query_invocation_id,
+ );
+ }
+
+ if unlikely(self.event_filter_mask.contains(EventFilter::QUERY_CACHE_HITS)) {
+ cold_call(self, query_invocation_id);
+ }
}
/// Start profiling a query being blocked on a concurrent execution.
@@ -444,20 +449,15 @@ impl SelfProfilerRef {
&self,
event_kind: fn(&SelfProfiler) -> StringId,
query_invocation_id: QueryInvocationId,
- event_filter: EventFilter,
) {
- drop(self.exec(event_filter, |profiler| {
- let event_id = StringId::new_virtual(query_invocation_id.0);
- let thread_id = get_thread_id();
-
- profiler.profiler.record_instant_event(
- event_kind(profiler),
- EventId::from_virtual(event_id),
- thread_id,
- );
-
- TimingGuard::none()
- }));
+ let event_id = StringId::new_virtual(query_invocation_id.0);
+ let thread_id = get_thread_id();
+ let profiler = self.profiler.as_ref().unwrap();
+ profiler.profiler.record_instant_event(
+ event_kind(profiler),
+ EventId::from_virtual(event_id),
+ thread_id,
+ );
}
pub fn with_profiler(&self, f: impl FnOnce(&SelfProfiler)) {
diff --git a/compiler/rustc_data_structures/src/sorted_map/index_map.rs b/compiler/rustc_data_structures/src/sorted_map/index_map.rs
index 814e7c7fb..7d23ff519 100644
--- a/compiler/rustc_data_structures/src/sorted_map/index_map.rs
+++ b/compiler/rustc_data_structures/src/sorted_map/index_map.rs
@@ -100,6 +100,11 @@ impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V> {
(k == &key).then_some((i, v))
})
}
+
+ #[inline]
+ pub fn contains_key(&self, key: K) -> bool {
+ self.get_by_key(key).next().is_some()
+ }
}
impl<I: Idx, K: Eq, V: Eq> Eq for SortedIndexMultiMap<I, K, V> {}
diff --git a/compiler/rustc_data_structures/src/sorted_map/tests.rs b/compiler/rustc_data_structures/src/sorted_map/tests.rs
index 3cc250862..def7a7112 100644
--- a/compiler/rustc_data_structures/src/sorted_map/tests.rs
+++ b/compiler/rustc_data_structures/src/sorted_map/tests.rs
@@ -17,6 +17,10 @@ fn test_sorted_index_multi_map() {
assert_eq!(set.get_by_key(3).copied().collect::<Vec<_>>(), vec![0]);
assert!(set.get_by_key(4).next().is_none());
+ // `contains_key` works
+ assert!(set.contains_key(3));
+ assert!(!set.contains_key(4));
+
// `get_by_key` returns items in insertion order.
let twos: Vec<_> = set.get_by_key_enumerated(2).collect();
let idxs: Vec<usize> = twos.iter().map(|(i, _)| *i).collect();
diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs
index ae4836645..e0d77cdae 100644
--- a/compiler/rustc_data_structures/src/stable_hasher.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher.rs
@@ -486,6 +486,14 @@ impl<HCX> ToStableHashKey<HCX> for String {
}
}
+impl<HCX, T1: ToStableHashKey<HCX>, T2: ToStableHashKey<HCX>> ToStableHashKey<HCX> for (T1, T2) {
+ type KeyType = (T1::KeyType, T2::KeyType);
+ #[inline]
+ fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType {
+ (self.0.to_stable_hash_key(hcx), self.1.to_stable_hash_key(hcx))
+ }
+}
+
impl<CTX> HashStable<CTX> for bool {
#[inline]
fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
diff --git a/compiler/rustc_data_structures/src/stable_hasher/tests.rs b/compiler/rustc_data_structures/src/stable_hasher/tests.rs
index b0d66c32a..724be5888 100644
--- a/compiler/rustc_data_structures/src/stable_hasher/tests.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher/tests.rs
@@ -150,7 +150,7 @@ fn test_isize_compression() {
let hash_b = hash(&(b as isize, a as isize));
assert_ne!(
hash_a, hash_b,
- "The hash stayed the same when permuting values `{a}` and `{b}!",
+ "The hash stayed the same when permuting values `{a}` and `{b}`!",
);
}
diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs
index ed5341c40..31323c21d 100644
--- a/compiler/rustc_data_structures/src/sync.rs
+++ b/compiler/rustc_data_structures/src/sync.rs
@@ -26,13 +26,17 @@ 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 {}
pub auto trait Sync {}
- impl<T: ?Sized> Send for T {}
- impl<T: ?Sized> Sync for T {}
+ impl<T> Send for T {}
+ impl<T> Sync for T {}
#[macro_export]
macro_rules! rustc_erase_owner {
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 000000000..cbea4f059
--- /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);
+ }
+}