diff options
Diffstat (limited to 'compiler/rustc_data_structures/src')
12 files changed, 212 insertions, 38 deletions
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); + } +} |