diff options
Diffstat (limited to 'compiler/rustc_data_structures')
24 files changed, 481 insertions, 154 deletions
diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml index e3395df3590..ad296c97659 100644 --- a/compiler/rustc_data_structures/Cargo.toml +++ b/compiler/rustc_data_structures/Cargo.toml @@ -9,7 +9,7 @@ doctest = false [dependencies] arrayvec = { version = "0.7", default-features = false } ena = "0.14" -indexmap = "1.5.1" +indexmap = { version = "1.8.0", features = ["rustc-rayon"] } tracing = "0.1" jobserver_crate = { version = "0.1.13", package = "jobserver" } rustc_serialize = { path = "../rustc_serialize" } @@ -17,8 +17,8 @@ rustc_macros = { path = "../rustc_macros" } rustc_graphviz = { path = "../rustc_graphviz" } cfg-if = "0.1.2" stable_deref_trait = "1.0.0" -rayon = { version = "0.3.1", package = "rustc-rayon" } -rayon-core = { version = "0.3.1", package = "rustc-rayon-core" } +rayon = { version = "0.3.2", package = "rustc-rayon" } +rayon-core = { version = "0.3.2", package = "rustc-rayon-core" } rustc-hash = "1.1.0" smallvec = { version = "1.6.1", features = ["union", "may_dangle"] } rustc_index = { path = "../rustc_index", package = "rustc_index" } diff --git a/compiler/rustc_data_structures/src/binary_search_util/mod.rs b/compiler/rustc_data_structures/src/binary_search_util/mod.rs index ede5757a479..bf09b2f8eef 100644 --- a/compiler/rustc_data_structures/src/binary_search_util/mod.rs +++ b/compiler/rustc_data_structures/src/binary_search_util/mod.rs @@ -6,7 +6,7 @@ mod tests; /// function finds the range of elements that match the key. `data` /// must have been sorted as if by a call to `sort_by_key` for this to /// work. -pub fn binary_search_slice<E, K>(data: &'d [E], key_fn: impl Fn(&E) -> K, key: &K) -> &'d [E] +pub fn binary_search_slice<'d, E, K>(data: &'d [E], key_fn: impl Fn(&E) -> K, key: &K) -> &'d [E] where K: Ord, { diff --git a/compiler/rustc_data_structures/src/fingerprint.rs b/compiler/rustc_data_structures/src/fingerprint.rs index c0c0e7be3ca..525cd650dd2 100644 --- a/compiler/rustc_data_structures/src/fingerprint.rs +++ b/compiler/rustc_data_structures/src/fingerprint.rs @@ -142,17 +142,17 @@ impl_stable_hash_via_hash!(Fingerprint); impl<E: rustc_serialize::Encoder> Encodable<E> for Fingerprint { #[inline] fn encode(&self, s: &mut E) -> Result<(), E::Error> { - s.emit_raw_bytes(&self.to_le_bytes()[..])?; + s.emit_raw_bytes(&self.to_le_bytes())?; Ok(()) } } impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint { #[inline] - fn decode(d: &mut D) -> Result<Self, D::Error> { + fn decode(d: &mut D) -> Self { let mut bytes = [0u8; 16]; - d.read_raw_bytes_into(&mut bytes[..])?; - Ok(Fingerprint::from_le_bytes(bytes)) + d.read_raw_bytes_into(&mut bytes); + Fingerprint::from_le_bytes(bytes) } } @@ -195,8 +195,8 @@ impl<E: rustc_serialize::Encoder> Encodable<E> for PackedFingerprint { impl<D: rustc_serialize::Decoder> Decodable<D> for PackedFingerprint { #[inline] - fn decode(d: &mut D) -> Result<Self, D::Error> { - Fingerprint::decode(d).map(PackedFingerprint) + fn decode(d: &mut D) -> Self { + Self(Fingerprint::decode(d)) } } diff --git a/compiler/rustc_data_structures/src/functor.rs b/compiler/rustc_data_structures/src/functor.rs index 5b83ae31247..a3d3f988344 100644 --- a/compiler/rustc_data_structures/src/functor.rs +++ b/compiler/rustc_data_structures/src/functor.rs @@ -1,35 +1,32 @@ use rustc_index::vec::{Idx, IndexVec}; use std::mem; -use std::ptr; -pub trait IdFunctor { +pub trait IdFunctor: Sized { type Inner; - fn map_id<F>(self, f: F) -> Self + fn try_map_id<F, E>(self, f: F) -> Result<Self, E> where - F: FnMut(Self::Inner) -> Self::Inner; + F: FnMut(Self::Inner) -> Result<Self::Inner, E>; } impl<T> IdFunctor for Box<T> { type Inner = T; #[inline] - fn map_id<F>(self, mut f: F) -> Self + fn try_map_id<F, E>(self, mut f: F) -> Result<Self, E> where - F: FnMut(Self::Inner) -> Self::Inner, + F: FnMut(Self::Inner) -> Result<Self::Inner, E>, { let raw = Box::into_raw(self); - unsafe { + Ok(unsafe { // SAFETY: The raw pointer points to a valid value of type `T`. - let value = ptr::read(raw); + let value = raw.read(); // SAFETY: Converts `Box<T>` to `Box<MaybeUninit<T>>` which is the // inverse of `Box::assume_init()` and should be safe. - let mut raw: Box<mem::MaybeUninit<T>> = Box::from_raw(raw.cast()); + let raw: Box<mem::MaybeUninit<T>> = Box::from_raw(raw.cast()); // SAFETY: Write the mapped value back into the `Box`. - raw.write(f(value)); - // SAFETY: We just initialized `raw`. - raw.assume_init() - } + Box::write(raw, f(value)?) + }) } } @@ -37,23 +34,43 @@ impl<T> IdFunctor for Vec<T> { type Inner = T; #[inline] - fn map_id<F>(mut self, mut f: F) -> Self + fn try_map_id<F, E>(self, mut f: F) -> Result<Self, E> where - F: FnMut(Self::Inner) -> Self::Inner, + F: FnMut(Self::Inner) -> Result<Self::Inner, E>, { - // FIXME: We don't really care about panics here and leak - // far more than we should, but that should be fine for now. - let len = self.len(); + struct HoleVec<T> { + vec: Vec<mem::ManuallyDrop<T>>, + hole: Option<usize>, + } + + impl<T> Drop for HoleVec<T> { + fn drop(&mut self) { + unsafe { + for (index, slot) in self.vec.iter_mut().enumerate() { + if self.hole != Some(index) { + mem::ManuallyDrop::drop(slot); + } + } + } + } + } + unsafe { - self.set_len(0); - let start = self.as_mut_ptr(); - for i in 0..len { - let p = start.add(i); - ptr::write(p, f(ptr::read(p))); + let (ptr, length, capacity) = self.into_raw_parts(); + let vec = Vec::from_raw_parts(ptr.cast(), length, capacity); + let mut hole_vec = HoleVec { vec, hole: None }; + + for (index, slot) in hole_vec.vec.iter_mut().enumerate() { + hole_vec.hole = Some(index); + let original = mem::ManuallyDrop::take(slot); + let mapped = f(original)?; + *slot = mem::ManuallyDrop::new(mapped); + hole_vec.hole = None; } - self.set_len(len); + + mem::forget(hole_vec); + Ok(Vec::from_raw_parts(ptr, length, capacity)) } - self } } @@ -61,11 +78,11 @@ impl<T> IdFunctor for Box<[T]> { type Inner = T; #[inline] - fn map_id<F>(self, f: F) -> Self + fn try_map_id<F, E>(self, f: F) -> Result<Self, E> where - F: FnMut(Self::Inner) -> Self::Inner, + F: FnMut(Self::Inner) -> Result<Self::Inner, E>, { - Vec::from(self).map_id(f).into() + Vec::from(self).try_map_id(f).map(Into::into) } } @@ -73,10 +90,10 @@ impl<I: Idx, T> IdFunctor for IndexVec<I, T> { type Inner = T; #[inline] - fn map_id<F>(self, f: F) -> Self + fn try_map_id<F, E>(self, f: F) -> Result<Self, E> where - F: FnMut(Self::Inner) -> Self::Inner, + F: FnMut(Self::Inner) -> Result<Self::Inner, E>, { - IndexVec::from_raw(self.raw.map_id(f)) + self.raw.try_map_id(f).map(IndexVec::from_raw) } } diff --git a/compiler/rustc_data_structures/src/graph/dominators/mod.rs b/compiler/rustc_data_structures/src/graph/dominators/mod.rs index 1cd170599ba..0d2ae115cb0 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -1,11 +1,14 @@ //! Finding the dominators in a control-flow graph. //! -//! Algorithm based on Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy, -//! "A Simple, Fast Dominance Algorithm", -//! Rice Computer Science TS-06-33870, -//! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>. +//! Algorithm based on Loukas Georgiadis, +//! "Linear-Time Algorithms for Dominators and Related Problems", +//! <ftp://ftp.cs.princeton.edu/techreports/2005/737.pdf> +//! +//! Additionally useful is the original Lengauer-Tarjan paper on this subject, +//! "A Fast Algorithm for Finding Dominators in a Flowgraph" +//! Thomas Lengauer and Robert Endre Tarjan. +//! <https://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf> -use super::iterate::reverse_post_order; use super::ControlFlowGraph; use rustc_index::vec::{Idx, IndexVec}; use std::cmp::Ordering; @@ -13,69 +16,239 @@ use std::cmp::Ordering; #[cfg(test)] mod tests; -pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> { - let start_node = graph.start_node(); - let rpo = reverse_post_order(&graph, start_node); - dominators_given_rpo(graph, &rpo) +struct PreOrderFrame<Iter> { + pre_order_idx: PreorderIndex, + iter: Iter, } -fn dominators_given_rpo<G: ControlFlowGraph>(graph: G, rpo: &[G::Node]) -> Dominators<G::Node> { - let start_node = graph.start_node(); - assert_eq!(rpo[0], start_node); +rustc_index::newtype_index! { + struct PreorderIndex { .. } +} +pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> { // compute the post order index (rank) for each node let mut post_order_rank = IndexVec::from_elem_n(0, graph.num_nodes()); - for (index, node) in rpo.iter().rev().cloned().enumerate() { - post_order_rank[node] = index; - } - let mut immediate_dominators = IndexVec::from_elem_n(None, graph.num_nodes()); - immediate_dominators[start_node] = Some(start_node); - - let mut changed = true; - while changed { - changed = false; - - for &node in &rpo[1..] { - let mut new_idom = None; - for pred in graph.predecessors(node) { - if immediate_dominators[pred].is_some() { - // (*) dominators for `pred` have been calculated - new_idom = Some(if let Some(new_idom) = new_idom { - intersect(&post_order_rank, &immediate_dominators, new_idom, pred) - } else { - pred - }); - } - } + // We allocate capacity for the full set of nodes, because most of the time + // most of the nodes *are* reachable. + let mut parent: IndexVec<PreorderIndex, PreorderIndex> = + IndexVec::with_capacity(graph.num_nodes()); + + let mut stack = vec![PreOrderFrame { + pre_order_idx: PreorderIndex::new(0), + iter: graph.successors(graph.start_node()), + }]; + let mut pre_order_to_real: IndexVec<PreorderIndex, G::Node> = + IndexVec::with_capacity(graph.num_nodes()); + let mut real_to_pre_order: IndexVec<G::Node, Option<PreorderIndex>> = + IndexVec::from_elem_n(None, graph.num_nodes()); + pre_order_to_real.push(graph.start_node()); + parent.push(PreorderIndex::new(0)); // the parent of the root node is the root for now. + real_to_pre_order[graph.start_node()] = Some(PreorderIndex::new(0)); + let mut post_order_idx = 0; + + // Traverse the graph, collecting a number of things: + // + // * Preorder mapping (to it, and back to the actual ordering) + // * Postorder mapping (used exclusively for rank_partial_cmp on the final product) + // * Parents for each vertex in the preorder tree + // + // These are all done here rather than through one of the 'standard' + // graph traversals to help make this fast. + 'recurse: while let Some(frame) = stack.last_mut() { + while let Some(successor) = frame.iter.next() { + if real_to_pre_order[successor].is_none() { + let pre_order_idx = pre_order_to_real.push(successor); + real_to_pre_order[successor] = Some(pre_order_idx); + parent.push(frame.pre_order_idx); + stack.push(PreOrderFrame { pre_order_idx, iter: graph.successors(successor) }); - if new_idom != immediate_dominators[node] { - immediate_dominators[node] = new_idom; - changed = true; + continue 'recurse; } } + post_order_rank[pre_order_to_real[frame.pre_order_idx]] = post_order_idx; + post_order_idx += 1; + + stack.pop(); } - Dominators { post_order_rank, immediate_dominators } -} + let reachable_vertices = pre_order_to_real.len(); + + let mut idom = IndexVec::from_elem_n(PreorderIndex::new(0), reachable_vertices); + let mut semi = IndexVec::from_fn_n(std::convert::identity, reachable_vertices); + let mut label = semi.clone(); + let mut bucket = IndexVec::from_elem_n(vec![], reachable_vertices); + let mut lastlinked = None; + + // We loop over vertices in reverse preorder. This implements the pseudocode + // of the simple Lengauer-Tarjan algorithm. A few key facts are noted here + // which are helpful for understanding the code (full proofs and such are + // found in various papers, including one cited at the top of this file). + // + // For each vertex w (which is not the root), + // * semi[w] is a proper ancestor of the vertex w (i.e., semi[w] != w) + // * idom[w] is an ancestor of semi[w] (i.e., idom[w] may equal semi[w]) + // + // An immediate dominator of w (idom[w]) is a vertex v where v dominates w + // and every other dominator of w dominates v. (Every vertex except the root has + // a unique immediate dominator.) + // + // A semidominator for a given vertex w (semi[w]) is the vertex v with minimum + // preorder number such that there exists a path from v to w in which all elements (other than w) have + // preorder numbers greater than w (i.e., this path is not the tree path to + // w). + for w in (PreorderIndex::new(1)..PreorderIndex::new(reachable_vertices)).rev() { + // Optimization: process buckets just once, at the start of the + // iteration. Do not explicitly empty the bucket (even though it will + // not be used again), to save some instructions. + // + // The bucket here contains the vertices whose semidominator is the + // vertex w, which we are guaranteed to have found: all vertices who can + // be semidominated by w must have a preorder number exceeding w, so + // they have been placed in the bucket. + // + // We compute a partial set of immediate dominators here. + let z = parent[w]; + for &v in bucket[z].iter() { + // This uses the result of Lemma 5 from section 2 from the original + // 1979 paper, to compute either the immediate or relative dominator + // for a given vertex v. + // + // eval returns a vertex y, for which semi[y] is minimum among + // vertices semi[v] +> y *> v. Note that semi[v] = z as we're in the + // z bucket. + // + // Given such a vertex y, semi[y] <= semi[v] and idom[y] = idom[v]. + // If semi[y] = semi[v], though, idom[v] = semi[v]. + // + // Using this, we can either set idom[v] to be: + // * semi[v] (i.e. z), if semi[y] is z + // * idom[y], otherwise + // + // We don't directly set to idom[y] though as it's not necessarily + // known yet. The second preorder traversal will cleanup by updating + // the idom for any that were missed in this pass. + let y = eval(&mut parent, lastlinked, &semi, &mut label, v); + idom[v] = if semi[y] < z { y } else { z }; + } + + // This loop computes the semi[w] for w. + semi[w] = w; + for v in graph.predecessors(pre_order_to_real[w]) { + let v = real_to_pre_order[v].unwrap(); + + // eval returns a vertex x from which semi[x] is minimum among + // vertices semi[v] +> x *> v. + // + // From Lemma 4 from section 2, we know that the semidominator of a + // vertex w is the minimum (by preorder number) vertex of the + // following: + // + // * direct predecessors of w with preorder number less than w + // * semidominators of u such that u > w and there exists (v, w) + // such that u *> v + // + // This loop therefore identifies such a minima. Note that any + // semidominator path to w must have all but the first vertex go + // through vertices numbered greater than w, so the reverse preorder + // traversal we are using guarantees that all of the information we + // might need is available at this point. + // + // The eval call will give us semi[x], which is either: + // + // * v itself, if v has not yet been processed + // * A possible 'best' semidominator for w. + let x = eval(&mut parent, lastlinked, &semi, &mut label, v); + semi[w] = std::cmp::min(semi[w], semi[x]); + } + // semi[w] is now semidominator(w) and won't change any more. -fn intersect<Node: Idx>( - post_order_rank: &IndexVec<Node, usize>, - immediate_dominators: &IndexVec<Node, Option<Node>>, - mut node1: Node, - mut node2: Node, -) -> Node { - while node1 != node2 { - while post_order_rank[node1] < post_order_rank[node2] { - node1 = immediate_dominators[node1].unwrap(); + // Optimization: Do not insert into buckets if parent[w] = semi[w], as + // we then immediately know the idom. + // + // If we don't yet know the idom directly, then push this vertex into + // our semidominator's bucket, where it will get processed at a later + // stage to compute its immediate dominator. + if parent[w] != semi[w] { + bucket[semi[w]].push(w); + } else { + idom[w] = parent[w]; } - while post_order_rank[node2] < post_order_rank[node1] { - node2 = immediate_dominators[node2].unwrap(); + // Optimization: We share the parent array between processed and not + // processed elements; lastlinked represents the divider. + lastlinked = Some(w); + } + + // Finalize the idoms for any that were not fully settable during initial + // traversal. + // + // If idom[w] != semi[w] then we know that we've stored vertex y from above + // into idom[w]. It is known to be our 'relative dominator', which means + // that it's one of w's ancestors and has the same immediate dominator as w, + // so use that idom. + for w in PreorderIndex::new(1)..PreorderIndex::new(reachable_vertices) { + if idom[w] != semi[w] { + idom[w] = idom[idom[w]]; } } - node1 + let mut immediate_dominators = IndexVec::from_elem_n(None, graph.num_nodes()); + for (idx, node) in pre_order_to_real.iter_enumerated() { + immediate_dominators[*node] = Some(pre_order_to_real[idom[idx]]); + } + + Dominators { post_order_rank, immediate_dominators } +} + +/// Evaluate the link-eval virtual forest, providing the currently minimum semi +/// value for the passed `node` (which may be itself). +/// +/// This maintains that for every vertex v, `label[v]` is such that: +/// +/// ```text +/// semi[eval(v)] = min { semi[label[u]] | root_in_forest(v) +> u *> v } +/// ``` +/// +/// where `+>` is a proper ancestor and `*>` is just an ancestor. +#[inline] +fn eval( + ancestor: &mut IndexVec<PreorderIndex, PreorderIndex>, + lastlinked: Option<PreorderIndex>, + semi: &IndexVec<PreorderIndex, PreorderIndex>, + label: &mut IndexVec<PreorderIndex, PreorderIndex>, + node: PreorderIndex, +) -> PreorderIndex { + if is_processed(node, lastlinked) { + compress(ancestor, lastlinked, semi, label, node); + label[node] + } else { + node + } +} + +#[inline] +fn is_processed(v: PreorderIndex, lastlinked: Option<PreorderIndex>) -> bool { + if let Some(ll) = lastlinked { v >= ll } else { false } +} + +#[inline] +fn compress( + ancestor: &mut IndexVec<PreorderIndex, PreorderIndex>, + lastlinked: Option<PreorderIndex>, + semi: &IndexVec<PreorderIndex, PreorderIndex>, + label: &mut IndexVec<PreorderIndex, PreorderIndex>, + v: PreorderIndex, +) { + assert!(is_processed(v, lastlinked)); + let u = ancestor[v]; + if is_processed(u, lastlinked) { + compress(ancestor, lastlinked, semi, label, u); + if semi[label[u]] < semi[label[v]] { + label[v] = label[u]; + } + ancestor[v] = ancestor[u]; + } } #[derive(Clone, Debug)] diff --git a/compiler/rustc_data_structures/src/graph/dominators/tests.rs b/compiler/rustc_data_structures/src/graph/dominators/tests.rs index 1160df5186b..ff31d8f7fdc 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/tests.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/tests.rs @@ -32,3 +32,14 @@ fn paper() { assert_eq!(immediate_dominators[5], Some(6)); assert_eq!(immediate_dominators[6], Some(6)); } + +#[test] +fn paper_slt() { + // example from the paper: + let graph = TestGraph::new( + 1, + &[(1, 2), (1, 3), (2, 3), (2, 7), (3, 4), (3, 6), (4, 5), (5, 4), (6, 7), (7, 8), (8, 5)], + ); + + dominators(&graph); +} diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index a9db3497b23..57007611a76 100644 --- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -79,7 +79,7 @@ where visited: BitSet<G::Node>, } -impl<G> DepthFirstSearch<'graph, G> +impl<'graph, G> DepthFirstSearch<'graph, G> where G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, { @@ -209,7 +209,7 @@ where settled: BitSet<G::Node>, } -impl<G> TriColorDepthFirstSearch<'graph, G> +impl<'graph, G> TriColorDepthFirstSearch<'graph, G> where G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, { @@ -276,7 +276,7 @@ where } } -impl<G> TriColorDepthFirstSearch<'graph, G> +impl<G> TriColorDepthFirstSearch<'_, G> where G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode, { diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index b84f28b6a9e..7099ca7eb88 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -9,6 +9,7 @@ use crate::fx::FxHashSet; use crate::graph::vec_graph::VecGraph; use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; use rustc_index::vec::{Idx, IndexVec}; +use std::cmp::Ord; use std::ops::Range; #[cfg(test)] @@ -38,7 +39,7 @@ struct SccData<S: Idx> { all_successors: Vec<S>, } -impl<N: Idx, S: Idx> Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> Sccs<N, S> { pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self { SccsConstruction::construct(graph) } @@ -85,7 +86,7 @@ impl<N: Idx, S: Idx> DirectedGraph for Sccs<N, S> { type Node = S; } -impl<N: Idx, S: Idx> WithNumNodes for Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> WithNumNodes for Sccs<N, S> { fn num_nodes(&self) -> usize { self.num_sccs() } @@ -97,13 +98,13 @@ impl<N: Idx, S: Idx> WithNumEdges for Sccs<N, S> { } } -impl<N: Idx, S: Idx> GraphSuccessors<'graph> for Sccs<N, S> { +impl<'graph, N: Idx, S: Idx> GraphSuccessors<'graph> for Sccs<N, S> { type Item = S; type Iter = std::iter::Cloned<std::slice::Iter<'graph, S>>; } -impl<N: Idx, S: Idx> WithSuccessors for Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> WithSuccessors for Sccs<N, S> { fn successors(&self, node: S) -> <Self as GraphSuccessors<'_>>::Iter { self.successors(node).iter().cloned() } diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs index 4ed88878418..3d91bcade59 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs @@ -1,3 +1,5 @@ +use std::cmp::Ord; + use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; use rustc_index::vec::{Idx, IndexVec}; @@ -17,7 +19,7 @@ pub struct VecGraph<N: Idx> { edge_targets: Vec<N>, } -impl<N: Idx> VecGraph<N> { +impl<N: Idx + Ord> VecGraph<N> { pub fn new(num_nodes: usize, mut edge_pairs: Vec<(N, N)>) -> Self { // Sort the edges by the source -- this is important. edge_pairs.sort(); @@ -94,13 +96,13 @@ impl<N: Idx> WithNumEdges for VecGraph<N> { } } -impl<N: Idx> GraphSuccessors<'graph> for VecGraph<N> { +impl<'graph, N: Idx> GraphSuccessors<'graph> for VecGraph<N> { type Item = N; type Iter = std::iter::Cloned<std::slice::Iter<'graph, N>>; } -impl<N: Idx> WithSuccessors for VecGraph<N> { +impl<N: Idx + Ord> WithSuccessors for VecGraph<N> { fn successors(&self, node: N) -> <Self as GraphSuccessors<'_>>::Iter { self.successors(node).iter().cloned() } diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index 77784bf1705..181e5180d53 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -15,16 +15,15 @@ #![feature(core_intrinsics)] #![feature(extend_one)] #![feature(hash_raw_entry)] -#![feature(in_band_lifetimes)] #![feature(maybe_uninit_uninit_array)] #![feature(min_specialization)] #![feature(never_type)] #![feature(type_alias_impl_trait)] #![feature(new_uninit)] -#![feature(nll)] #![feature(once_cell)] #![feature(test)] #![feature(thread_id_value)] +#![feature(vec_into_raw_parts)] #![allow(rustc::default_hash_types)] #![deny(unaligned_references)] diff --git a/compiler/rustc_data_structures/src/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs index c21939209fc..fd6ff086b08 100644 --- a/compiler/rustc_data_structures/src/profiling.rs +++ b/compiler/rustc_data_structures/src/profiling.rs @@ -649,7 +649,7 @@ impl Drop for VerboseTimingGuard<'_> { fn drop(&mut self) { if let Some((start_time, start_rss, ref message)) = self.start_and_message { let end_rss = get_resident_set_size(); - print_time_passes_entry(&message[..], start_time.elapsed(), start_rss, end_rss); + print_time_passes_entry(&message, start_time.elapsed(), start_rss, end_rss); } } } diff --git a/compiler/rustc_data_structures/src/small_c_str.rs b/compiler/rustc_data_structures/src/small_c_str.rs index 4a089398ce6..33e72914e19 100644 --- a/compiler/rustc_data_structures/src/small_c_str.rs +++ b/compiler/rustc_data_structures/src/small_c_str.rs @@ -46,7 +46,7 @@ impl SmallCStr { #[inline] pub fn as_c_str(&self) -> &ffi::CStr { - unsafe { ffi::CStr::from_bytes_with_nul_unchecked(&self.data[..]) } + unsafe { ffi::CStr::from_bytes_with_nul_unchecked(&self.data) } } #[inline] 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 e92db9ea128..593316e2699 100644 --- a/compiler/rustc_data_structures/src/sorted_map/index_map.rs +++ b/compiler/rustc_data_structures/src/sorted_map/index_map.rs @@ -34,39 +34,47 @@ pub struct SortedIndexMultiMap<I: Idx, K, V> { } impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V> { + #[inline] pub fn new() -> Self { SortedIndexMultiMap { items: IndexVec::new(), idx_sorted_by_item_key: Vec::new() } } + #[inline] pub fn len(&self) -> usize { self.items.len() } + #[inline] pub fn is_empty(&self) -> bool { self.items.is_empty() } /// Returns an iterator over the items in the map in insertion order. + #[inline] pub fn into_iter(self) -> impl DoubleEndedIterator<Item = (K, V)> { self.items.into_iter() } /// Returns an iterator over the items in the map in insertion order along with their indices. + #[inline] pub fn into_iter_enumerated(self) -> impl DoubleEndedIterator<Item = (I, (K, V))> { self.items.into_iter_enumerated() } /// Returns an iterator over the items in the map in insertion order. + #[inline] pub fn iter(&self) -> impl '_ + DoubleEndedIterator<Item = (&K, &V)> { self.items.iter().map(|(ref k, ref v)| (k, v)) } /// Returns an iterator over the items in the map in insertion order along with their indices. + #[inline] pub fn iter_enumerated(&self) -> impl '_ + DoubleEndedIterator<Item = (I, (&K, &V))> { self.items.iter_enumerated().map(|(i, (ref k, ref v))| (i, (k, v))) } /// Returns the item in the map with the given index. + #[inline] pub fn get(&self, idx: I) -> Option<&(K, V)> { self.items.get(idx) } @@ -75,7 +83,8 @@ impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V> { /// /// If there are multiple items that are equivalent to `key`, they will be yielded in /// insertion order. - pub fn get_by_key(&'a self, key: K) -> impl 'a + Iterator<Item = &'a V> { + #[inline] + pub fn get_by_key(&self, key: K) -> impl Iterator<Item = &V> + '_ { self.get_by_key_enumerated(key).map(|(_, v)| v) } @@ -84,7 +93,8 @@ impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V> { /// /// If there are multiple items that are equivalent to `key`, they will be yielded in /// insertion order. - pub fn get_by_key_enumerated(&'a self, key: K) -> impl '_ + Iterator<Item = (I, &V)> { + #[inline] + pub fn get_by_key_enumerated(&self, key: K) -> impl Iterator<Item = (I, &V)> + '_ { let lower_bound = self.idx_sorted_by_item_key.partition_point(|&i| self.items[i].0 < key); self.idx_sorted_by_item_key[lower_bound..].iter().map_while(move |&i| { let (k, v) = &self.items[i]; diff --git a/compiler/rustc_data_structures/src/sso/map.rs b/compiler/rustc_data_structures/src/sso/map.rs index 2de05cd4e56..ec6a62016a8 100644 --- a/compiler/rustc_data_structures/src/sso/map.rs +++ b/compiler/rustc_data_structures/src/sso/map.rs @@ -423,14 +423,14 @@ impl<K, V> IntoIterator for SsoHashMap<K, V> { /// adapts Item of array reference iterator to Item of hashmap reference iterator. #[inline(always)] -fn adapt_array_ref_it<K, V>(pair: &'a (K, V)) -> (&'a K, &'a V) { +fn adapt_array_ref_it<K, V>(pair: &(K, V)) -> (&K, &V) { let (a, b) = pair; (a, b) } /// adapts Item of array mut reference iterator to Item of hashmap mut reference iterator. #[inline(always)] -fn adapt_array_mut_it<K, V>(pair: &'a mut (K, V)) -> (&'a K, &'a mut V) { +fn adapt_array_mut_it<K, V>(pair: &mut (K, V)) -> (&K, &mut V) { let (a, b) = pair; (a, b) } diff --git a/compiler/rustc_data_structures/src/sso/set.rs b/compiler/rustc_data_structures/src/sso/set.rs index 29baf4e1ddb..f71522d3714 100644 --- a/compiler/rustc_data_structures/src/sso/set.rs +++ b/compiler/rustc_data_structures/src/sso/set.rs @@ -75,7 +75,7 @@ impl<T> SsoHashSet<T> { /// An iterator visiting all elements in arbitrary order. /// The iterator element type is `&'a T`. #[inline] - pub fn iter(&'a self) -> impl Iterator<Item = &'a T> { + pub fn iter(&self) -> impl Iterator<Item = &T> { self.into_iter() } diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs index f800ec6a6a1..9c09a7f5f82 100644 --- a/compiler/rustc_data_structures/src/stable_hasher.rs +++ b/compiler/rustc_data_structures/src/stable_hasher.rs @@ -42,6 +42,7 @@ impl StableHasher { } impl StableHasherResult for u128 { + #[inline] fn finish(hasher: StableHasher) -> Self { let (_0, _1) = hasher.finalize(); u128::from(_0) | (u128::from(_1) << 64) @@ -49,6 +50,7 @@ impl StableHasherResult for u128 { } impl StableHasherResult for u64 { + #[inline] fn finish(hasher: StableHasher) -> Self { hasher.finalize().0 } @@ -377,9 +379,8 @@ impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> { impl<CTX> HashStable<CTX> for str { #[inline] - fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) { - self.len().hash(hasher); - self.as_bytes().hash(hasher); + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + self.as_bytes().hash_stable(ctx, hasher); } } @@ -476,14 +477,14 @@ where } impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> { - fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { - self.words().hash_stable(ctx, hasher); + fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { + ::std::hash::Hash::hash(self, hasher); } } impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> { - fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { - self.words().hash_stable(ctx, hasher); + fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { + ::std::hash::Hash::hash(self, hasher); } } @@ -507,7 +508,11 @@ where { #[inline] fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { - hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key); + stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| { + let key = key.to_stable_hash_key(hcx); + key.hash_stable(hcx, hasher); + value.hash_stable(hcx, hasher); + }); } } @@ -517,9 +522,10 @@ where R: BuildHasher, { fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { - let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect(); - keys.sort_unstable(); - keys.hash_stable(hcx, hasher); + stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| { + let key = key.to_stable_hash_key(hcx); + key.hash_stable(hcx, hasher); + }); } } @@ -529,10 +535,11 @@ where V: HashStable<HCX>, { fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { - let mut entries: Vec<_> = - self.iter().map(|(k, v)| (k.to_stable_hash_key(hcx), v)).collect(); - entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2)); - entries.hash_stable(hcx, hasher); + stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| { + let key = key.to_stable_hash_key(hcx); + key.hash_stable(hcx, hasher); + value.hash_stable(hcx, hasher); + }); } } @@ -541,25 +548,57 @@ where K: ToStableHashKey<HCX>, { fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { - let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect(); - keys.sort_unstable(); - keys.hash_stable(hcx, hasher); + stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| { + let key = key.to_stable_hash_key(hcx); + key.hash_stable(hcx, hasher); + }); } } -pub fn hash_stable_hashmap<HCX, K, V, R, SK, F>( +fn stable_hash_reduce<HCX, I, C, F>( hcx: &mut HCX, hasher: &mut StableHasher, - map: &::std::collections::HashMap<K, V, R>, - to_stable_hash_key: F, + mut collection: C, + length: usize, + hash_function: F, ) where - K: Eq, - V: HashStable<HCX>, - R: BuildHasher, - SK: HashStable<HCX> + Ord, - F: Fn(&K, &HCX) -> SK, + C: Iterator<Item = I>, + F: Fn(&mut StableHasher, &mut HCX, I), { - let mut entries: Vec<_> = map.iter().map(|(k, v)| (to_stable_hash_key(k, hcx), v)).collect(); - entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2)); - entries.hash_stable(hcx, hasher); + length.hash_stable(hcx, hasher); + + match length { + 1 => { + hash_function(hasher, hcx, collection.next().unwrap()); + } + _ => { + let hash = collection + .map(|value| { + let mut hasher = StableHasher::new(); + hash_function(&mut hasher, hcx, value); + hasher.finish::<u128>() + }) + .reduce(|accum, value| accum.wrapping_add(value)); + hash.hash_stable(hcx, hasher); + } + } +} + +#[derive(PartialEq, Eq, Clone, Copy, Hash, Debug)] +pub enum NodeIdHashingMode { + Ignore, + HashDefPath, +} + +/// Controls what data we do or not not hash. +/// Whenever a `HashStable` implementation caches its +/// result, it needs to include `HashingControls` as part +/// of the key, to ensure that is does not produce an incorrect +/// result (for example, using a `Fingerprint` produced while +/// hashing `Span`s when a `Fingeprint` without `Span`s is +/// being requested) +#[derive(Clone, Hash, Eq, PartialEq, Debug)] +pub struct HashingControls { + pub hash_spans: bool, + pub node_id_hashing_mode: NodeIdHashingMode, } diff --git a/compiler/rustc_data_structures/src/stable_hasher/tests.rs b/compiler/rustc_data_structures/src/stable_hasher/tests.rs index cd6ff96a555..31190363eb6 100644 --- a/compiler/rustc_data_structures/src/stable_hasher/tests.rs +++ b/compiler/rustc_data_structures/src/stable_hasher/tests.rs @@ -71,3 +71,72 @@ fn test_hash_isize() { assert_eq!(h.finalize(), expected); } + +fn hash<T: HashStable<()>>(t: &T) -> u128 { + let mut h = StableHasher::new(); + let ctx = &mut (); + t.hash_stable(ctx, &mut h); + h.finish() +} + +// Check that bit set hash includes the domain size. +#[test] +fn test_hash_bit_set() { + use rustc_index::bit_set::BitSet; + let a: BitSet<usize> = BitSet::new_empty(1); + let b: BitSet<usize> = BitSet::new_empty(2); + assert_ne!(a, b); + assert_ne!(hash(&a), hash(&b)); +} + +// Check that bit matrix hash includes the matrix dimensions. +#[test] +fn test_hash_bit_matrix() { + use rustc_index::bit_set::BitMatrix; + let a: BitMatrix<usize, usize> = BitMatrix::new(1, 1); + let b: BitMatrix<usize, usize> = BitMatrix::new(1, 2); + assert_ne!(a, b); + assert_ne!(hash(&a), hash(&b)); +} + +// Check that exchanging the value of two adjacent fields changes the hash. +#[test] +fn test_attribute_permutation() { + macro_rules! test_type { + ($ty: ty) => {{ + struct Foo { + a: $ty, + b: $ty, + } + + impl<CTX> HashStable<CTX> for Foo { + fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { + self.a.hash_stable(hcx, hasher); + self.b.hash_stable(hcx, hasher); + } + } + + #[allow(overflowing_literals)] + let mut item = Foo { a: 0xFF, b: 0xFF_FF }; + let hash_a = hash(&item); + std::mem::swap(&mut item.a, &mut item.b); + let hash_b = hash(&item); + assert_ne!( + hash_a, + hash_b, + "The hash stayed the same after values were swapped for type `{}`!", + stringify!($ty) + ); + }}; + } + + test_type!(u16); + test_type!(u32); + test_type!(u64); + test_type!(u128); + + test_type!(i16); + test_type!(i32); + test_type!(i64); + test_type!(i128); +} diff --git a/compiler/rustc_data_structures/src/steal.rs b/compiler/rustc_data_structures/src/steal.rs index a1ffbae8b15..a3ece655047 100644 --- a/compiler/rustc_data_structures/src/steal.rs +++ b/compiler/rustc_data_structures/src/steal.rs @@ -34,7 +34,7 @@ impl<T> Steal<T> { #[track_caller] pub fn borrow(&self) -> MappedReadGuard<'_, T> { let borrow = self.value.borrow(); - if let None = &*borrow { + if borrow.is_none() { panic!("attempted to read from stolen value: {}", std::any::type_name::<T>()); } ReadGuard::map(borrow, |opt| opt.as_ref().unwrap()) diff --git a/compiler/rustc_data_structures/src/svh.rs b/compiler/rustc_data_structures/src/svh.rs index ce90fbacaa4..12ef286091c 100644 --- a/compiler/rustc_data_structures/src/svh.rs +++ b/compiler/rustc_data_structures/src/svh.rs @@ -55,8 +55,8 @@ impl<S: Encoder> Encodable<S> for Svh { } impl<D: Decoder> Decodable<D> for Svh { - fn decode(d: &mut D) -> Result<Svh, D::Error> { - d.read_u64().map(u64::from_le).map(Svh::new) + fn decode(d: &mut D) -> Svh { + Svh::new(u64::from_le(d.read_u64())) } } diff --git a/compiler/rustc_data_structures/src/tagged_ptr/copy.rs b/compiler/rustc_data_structures/src/tagged_ptr/copy.rs index d63bcdb3c2b..e1d3e0bd35a 100644 --- a/compiler/rustc_data_structures/src/tagged_ptr/copy.rs +++ b/compiler/rustc_data_structures/src/tagged_ptr/copy.rs @@ -94,9 +94,11 @@ where // SAFETY: pointer_raw returns the original pointer unsafe { std::mem::transmute_copy(&self.pointer_raw()) } } + #[inline] pub fn tag(&self) -> T { unsafe { T::from_usize(self.packed.get() >> Self::TAG_BIT_SHIFT) } } + #[inline] pub fn set_tag(&mut self, tag: T) { let mut packed = self.packed.get(); let new_tag = T::into_usize(tag) << Self::TAG_BIT_SHIFT; diff --git a/compiler/rustc_data_structures/src/thin_vec.rs b/compiler/rustc_data_structures/src/thin_vec.rs index b5d2d24736c..716259142d1 100644 --- a/compiler/rustc_data_structures/src/thin_vec.rs +++ b/compiler/rustc_data_structures/src/thin_vec.rs @@ -5,7 +5,7 @@ use std::iter::FromIterator; /// A vector type optimized for cases where this size is usually 0 (cf. `SmallVec`). /// The `Option<Box<..>>` wrapping allows us to represent a zero sized vector with `None`, /// which uses only a single (null) pointer. -#[derive(Clone, Encodable, Decodable, Debug)] +#[derive(Clone, Encodable, Decodable, Debug, Hash, Eq, PartialEq)] pub struct ThinVec<T>(Option<Box<Vec<T>>>); impl<T> ThinVec<T> { @@ -20,6 +20,13 @@ impl<T> ThinVec<T> { pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, T> { self.into_iter() } + + pub fn push(&mut self, item: T) { + match *self { + ThinVec(Some(ref mut vec)) => vec.push(item), + ThinVec(None) => *self = vec![item].into(), + } + } } impl<T> From<Vec<T>> for ThinVec<T> { @@ -101,10 +108,7 @@ impl<T> Extend<T> for ThinVec<T> { } fn extend_one(&mut self, item: T) { - match *self { - ThinVec(Some(ref mut vec)) => vec.push(item), - ThinVec(None) => *self = vec![item].into(), - } + self.push(item) } fn extend_reserve(&mut self, additional: usize) { diff --git a/compiler/rustc_data_structures/src/thin_vec/tests.rs b/compiler/rustc_data_structures/src/thin_vec/tests.rs index 5abfd939373..0221b9912bb 100644 --- a/compiler/rustc_data_structures/src/thin_vec/tests.rs +++ b/compiler/rustc_data_structures/src/thin_vec/tests.rs @@ -10,8 +10,8 @@ impl<T> ThinVec<T> { fn test_from_iterator() { assert_eq!(std::iter::empty().collect::<ThinVec<String>>().into_vec(), Vec::<String>::new()); assert_eq!(std::iter::once(42).collect::<ThinVec<_>>().into_vec(), vec![42]); - assert_eq!(vec![1, 2].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2]); - assert_eq!(vec![1, 2, 3].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2, 3]); + assert_eq!([1, 2].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2]); + assert_eq!([1, 2, 3].into_iter().collect::<ThinVec<_>>().into_vec(), vec![1, 2, 3]); } #[test] diff --git a/compiler/rustc_data_structures/src/vec_linked_list.rs b/compiler/rustc_data_structures/src/vec_linked_list.rs index 1cf030d852e..ce60d40b24b 100644 --- a/compiler/rustc_data_structures/src/vec_linked_list.rs +++ b/compiler/rustc_data_structures/src/vec_linked_list.rs @@ -2,8 +2,8 @@ use rustc_index::vec::{Idx, IndexVec}; pub fn iter<Ls>( first: Option<Ls::LinkIndex>, - links: &'a Ls, -) -> impl Iterator<Item = Ls::LinkIndex> + 'a + links: &Ls, +) -> impl Iterator<Item = Ls::LinkIndex> + '_ where Ls: Links, { diff --git a/compiler/rustc_data_structures/src/vec_map/tests.rs b/compiler/rustc_data_structures/src/vec_map/tests.rs index 9083de85982..458b60077dc 100644 --- a/compiler/rustc_data_structures/src/vec_map/tests.rs +++ b/compiler/rustc_data_structures/src/vec_map/tests.rs @@ -14,7 +14,7 @@ fn test_from_iterator() { ); assert_eq!(std::iter::once((42, true)).collect::<VecMap<_, _>>().into_vec(), vec![(42, true)]); assert_eq!( - vec![(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>().into_vec(), + [(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>().into_vec(), vec![(1, true), (2, false)] ); } @@ -41,7 +41,7 @@ fn test_insert() { #[test] fn test_get() { - let v = vec![(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>(); + let v = [(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>(); assert_eq!(v.get(&1), Some(&true)); assert_eq!(v.get(&2), Some(&false)); assert_eq!(v.get(&3), None); |