diff options
| author | bors <bors@rust-lang.org> | 2024-04-16 06:41:11 +0000 |
|---|---|---|
| committer | bors <bors@rust-lang.org> | 2024-04-16 06:41:11 +0000 |
| commit | 88d1a1c6fdf6e607606876cdab672eebdf6a3c71 (patch) | |
| tree | 438ae4e11b312666a2c073fff0184ec42aa7274f /compiler/rustc_data_structures/src | |
| parent | 2f08c2c96501990caab0e47a095d76ffd6a31f16 (diff) | |
| parent | 3d3a584e4d88a572d68d7996122cda69a38dcf2e (diff) | |
| download | rust-88d1a1c6fdf6e607606876cdab672eebdf6a3c71.tar.gz rust-88d1a1c6fdf6e607606876cdab672eebdf6a3c71.zip | |
Auto merge of #3469 - rust-lang:rustup-2024-04-16, r=RalfJung
Automatic Rustup
Diffstat (limited to 'compiler/rustc_data_structures/src')
8 files changed, 80 insertions, 143 deletions
diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index 9eb4b5278c0..7a77f2c0dbb 100644 --- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -1,4 +1,4 @@ -use super::{DirectedGraph, WithNumNodes, WithStartNode, WithSuccessors}; +use super::{DirectedGraph, StartNode, Successors}; use rustc_index::bit_set::BitSet; use rustc_index::{IndexSlice, IndexVec}; use std::ops::ControlFlow; @@ -6,14 +6,14 @@ use std::ops::ControlFlow; #[cfg(test)] mod tests; -pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>( +pub fn post_order_from<G: DirectedGraph + Successors>( graph: &G, start_node: G::Node, ) -> Vec<G::Node> { post_order_from_to(graph, start_node, None) } -pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>( +pub fn post_order_from_to<G: DirectedGraph + Successors>( graph: &G, start_node: G::Node, end_node: Option<G::Node>, @@ -27,7 +27,7 @@ pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>( result } -fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( +fn post_order_walk<G: DirectedGraph + Successors>( graph: &G, node: G::Node, result: &mut Vec<G::Node>, @@ -60,7 +60,7 @@ fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( } } -pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( +pub fn reverse_post_order<G: DirectedGraph + Successors>( graph: &G, start_node: G::Node, ) -> Vec<G::Node> { @@ -72,7 +72,7 @@ pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( /// A "depth-first search" iterator for a directed graph. pub struct DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { graph: &'graph G, stack: Vec<G::Node>, @@ -81,7 +81,7 @@ where impl<'graph, G> DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { pub fn new(graph: &'graph G) -> Self { Self { graph, stack: vec![], visited: BitSet::new_empty(graph.num_nodes()) } @@ -127,7 +127,7 @@ where impl<G> std::fmt::Debug for DepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut f = fmt.debug_set(); @@ -140,7 +140,7 @@ where impl<G> Iterator for DepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { type Item = G::Node; @@ -201,7 +201,7 @@ struct Event<N> { /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms pub struct TriColorDepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { graph: &'graph G, stack: Vec<Event<G::Node>>, @@ -211,7 +211,7 @@ where impl<'graph, G> TriColorDepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { pub fn new(graph: &'graph G) -> Self { TriColorDepthFirstSearch { @@ -278,7 +278,7 @@ where impl<G> TriColorDepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode, + G: ?Sized + DirectedGraph + Successors + StartNode, { /// Performs a depth-first search, starting from `G::start_node()`. /// diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs index e06ab2fe36b..3ae3023a91b 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -12,70 +12,43 @@ mod tests; pub trait DirectedGraph { type Node: Idx; -} -pub trait WithNumNodes: DirectedGraph { fn num_nodes(&self) -> usize; } -pub trait WithNumEdges: DirectedGraph { +pub trait NumEdges: DirectedGraph { fn num_edges(&self) -> usize; } -pub trait WithSuccessors: DirectedGraph -where - Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>, -{ - fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter; - - fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> - where - Self: WithNumNodes, - { - iterate::DepthFirstSearch::new(self).with_start_node(from) - } -} - -#[allow(unused_lifetimes)] -pub trait GraphSuccessors<'graph> { - type Item; - type Iter: Iterator<Item = Self::Item>; -} - -pub trait WithPredecessors: DirectedGraph -where - Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>, -{ - fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter; -} - -#[allow(unused_lifetimes)] -pub trait GraphPredecessors<'graph> { - type Item; - type Iter: Iterator<Item = Self::Item>; -} - -pub trait WithStartNode: DirectedGraph { +pub trait StartNode: DirectedGraph { fn start_node(&self) -> Self::Node; } -pub trait ControlFlowGraph: - DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes -{ - // convenient trait +pub trait Successors: DirectedGraph { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node>; } -impl<T> ControlFlowGraph for T where - T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes -{ +pub trait Predecessors: DirectedGraph { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node>; } +/// Alias for [`DirectedGraph`] + [`StartNode`] + [`Predecessors`] + [`Successors`]. +pub trait ControlFlowGraph: DirectedGraph + StartNode + Predecessors + Successors {} +impl<T> ControlFlowGraph for T where T: DirectedGraph + StartNode + Predecessors + Successors {} + /// Returns `true` if the graph has a cycle that is reachable from the start node. pub fn is_cyclic<G>(graph: &G) -> bool where - G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes, + G: ?Sized + DirectedGraph + StartNode + Successors, { iterate::TriColorDepthFirstSearch::new(graph) .run_from_start(&mut iterate::CycleDetector) .is_some() } + +pub fn depth_first_search<G>(graph: &G, from: G::Node) -> iterate::DepthFirstSearch<'_, G> +where + G: ?Sized + Successors, +{ + iterate::DepthFirstSearch::new(graph).with_start_node(from) +} diff --git a/compiler/rustc_data_structures/src/graph/reference.rs b/compiler/rustc_data_structures/src/graph/reference.rs index c259fe56c15..7a487552f53 100644 --- a/compiler/rustc_data_structures/src/graph/reference.rs +++ b/compiler/rustc_data_structures/src/graph/reference.rs @@ -2,38 +2,26 @@ use super::*; impl<'graph, G: DirectedGraph> DirectedGraph for &'graph G { type Node = G::Node; -} -impl<'graph, G: WithNumNodes> WithNumNodes for &'graph G { fn num_nodes(&self) -> usize { (**self).num_nodes() } } -impl<'graph, G: WithStartNode> WithStartNode for &'graph G { +impl<'graph, G: StartNode> StartNode for &'graph G { fn start_node(&self) -> Self::Node { (**self).start_node() } } -impl<'graph, G: WithSuccessors> WithSuccessors for &'graph G { - fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter { +impl<'graph, G: Successors> Successors for &'graph G { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { (**self).successors(node) } } -impl<'graph, G: WithPredecessors> WithPredecessors for &'graph G { - fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter { +impl<'graph, G: Predecessors> Predecessors for &'graph G { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { (**self).predecessors(node) } } - -impl<'iter, 'graph, G: WithPredecessors> GraphPredecessors<'iter> for &'graph G { - type Item = G::Node; - type Iter = <G as GraphPredecessors<'iter>>::Iter; -} - -impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph G { - type Item = G::Node; - type Iter = <G as GraphSuccessors<'iter>>::Iter; -} diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index b54d75f7ed7..5021e5e8fc0 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -7,7 +7,7 @@ use crate::fx::FxHashSet; use crate::graph::vec_graph::VecGraph; -use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; +use crate::graph::{DirectedGraph, NumEdges, Successors}; use rustc_index::{Idx, IndexSlice, IndexVec}; use std::ops::Range; @@ -39,7 +39,7 @@ pub struct SccData<S: Idx> { } impl<N: Idx, S: Idx + Ord> Sccs<N, S> { - pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self { + pub fn new(graph: &(impl DirectedGraph<Node = N> + Successors)) -> Self { SccsConstruction::construct(graph) } @@ -89,30 +89,22 @@ impl<N: Idx, S: Idx + Ord> Sccs<N, S> { } } -impl<N: Idx, S: Idx> DirectedGraph for Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> DirectedGraph for Sccs<N, S> { type Node = S; -} -impl<N: Idx, S: Idx + Ord> WithNumNodes for Sccs<N, S> { fn num_nodes(&self) -> usize { self.num_sccs() } } -impl<N: Idx, S: Idx> WithNumEdges for Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> NumEdges for Sccs<N, S> { fn num_edges(&self) -> usize { self.scc_data.all_successors.len() } } -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 + Ord> WithSuccessors for Sccs<N, S> { - fn successors(&self, node: S) -> <Self as GraphSuccessors<'_>>::Iter { +impl<N: Idx, S: Idx + Ord> Successors for Sccs<N, S> { + fn successors(&self, node: S) -> impl Iterator<Item = Self::Node> { self.successors(node).iter().cloned() } } @@ -158,7 +150,7 @@ impl<S: Idx> SccData<S> { } } -struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + WithSuccessors, S: Idx> { +struct SccsConstruction<'c, G: DirectedGraph + Successors, S: Idx> { graph: &'c G, /// The state of each node; used during walk to record the stack @@ -218,7 +210,7 @@ enum WalkReturn<S> { impl<'c, G, S> SccsConstruction<'c, G, S> where - G: DirectedGraph + WithNumNodes + WithSuccessors, + G: DirectedGraph + Successors, S: Idx, { /// Identifies SCCs in the graph `G` and computes the resulting diff --git a/compiler/rustc_data_structures/src/graph/tests.rs b/compiler/rustc_data_structures/src/graph/tests.rs index 7f4ef906b36..85c2703cc25 100644 --- a/compiler/rustc_data_structures/src/graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/tests.rs @@ -1,7 +1,5 @@ use crate::fx::FxHashMap; use std::cmp::max; -use std::iter; -use std::slice; use super::*; @@ -36,38 +34,26 @@ impl TestGraph { impl DirectedGraph for TestGraph { type Node = usize; -} -impl WithStartNode for TestGraph { - fn start_node(&self) -> usize { - self.start_node + fn num_nodes(&self) -> usize { + self.num_nodes } } -impl WithNumNodes for TestGraph { - fn num_nodes(&self) -> usize { - self.num_nodes +impl StartNode for TestGraph { + fn start_node(&self) -> usize { + self.start_node } } -impl WithPredecessors for TestGraph { - fn predecessors(&self, node: usize) -> <Self as GraphPredecessors<'_>>::Iter { +impl Predecessors for TestGraph { + fn predecessors(&self, node: usize) -> impl Iterator<Item = Self::Node> { self.predecessors[&node].iter().cloned() } } -impl WithSuccessors for TestGraph { - fn successors(&self, node: usize) -> <Self as GraphSuccessors<'_>>::Iter { +impl Successors for TestGraph { + fn successors(&self, node: usize) -> impl Iterator<Item = Self::Node> { self.successors[&node].iter().cloned() } } - -impl<'graph> GraphPredecessors<'graph> for TestGraph { - type Item = usize; - type Iter = iter::Cloned<slice::Iter<'graph, usize>>; -} - -impl<'graph> GraphSuccessors<'graph> for TestGraph { - type Item = usize; - type Iter = iter::Cloned<slice::Iter<'graph, usize>>; -} 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 00f6266ce1d..26c86469fad 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs @@ -1,4 +1,4 @@ -use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; +use crate::graph::{DirectedGraph, NumEdges, Successors}; use rustc_index::{Idx, IndexVec}; #[cfg(test)] @@ -80,28 +80,20 @@ impl<N: Idx + Ord> VecGraph<N> { impl<N: Idx> DirectedGraph for VecGraph<N> { type Node = N; -} -impl<N: Idx> WithNumNodes for VecGraph<N> { fn num_nodes(&self) -> usize { self.node_starts.len() - 1 } } -impl<N: Idx> WithNumEdges for VecGraph<N> { +impl<N: Idx> NumEdges for VecGraph<N> { fn num_edges(&self) -> usize { self.edge_targets.len() } } -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 + Ord> WithSuccessors for VecGraph<N> { - fn successors(&self, node: N) -> <Self as GraphSuccessors<'_>>::Iter { +impl<N: Idx + Ord> Successors for VecGraph<N> { + fn successors(&self, node: N) -> impl Iterator<Item = Self::Node> { self.successors(node).iter().cloned() } } diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs index 7c866da6009..87c8d25f094 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs @@ -1,3 +1,5 @@ +use crate::graph; + use super::*; fn create_graph() -> VecGraph<usize> { @@ -37,6 +39,6 @@ fn successors() { #[test] fn dfs() { let graph = create_graph(); - let dfs: Vec<_> = graph.depth_first_search(0).collect(); + let dfs: Vec<_> = graph::depth_first_search(&graph, 0).collect(); assert_eq!(dfs, vec![0, 1, 3, 4, 2]); } diff --git a/compiler/rustc_data_structures/src/sip128.rs b/compiler/rustc_data_structures/src/sip128.rs index 4a0ed87f77c..4c9acfe0f71 100644 --- a/compiler/rustc_data_structures/src/sip128.rs +++ b/compiler/rustc_data_structures/src/sip128.rs @@ -1,5 +1,8 @@ //! This is a copy of `core::hash::sip` adapted to providing 128 bit hashes. +// This code is very hot and uses lots of arithmetic, avoid overflow checks for performance. +// See https://github.com/rust-lang/rust/pull/119440#issuecomment-1874255727 +use rustc_serialize::int_overflow::{DebugStrictAdd, DebugStrictSub}; use std::hash::Hasher; use std::mem::{self, MaybeUninit}; use std::ptr; @@ -103,19 +106,19 @@ unsafe fn copy_nonoverlapping_small(src: *const u8, dst: *mut u8, count: usize) } let mut i = 0; - if i + 3 < count { + if i.debug_strict_add(3) < count { ptr::copy_nonoverlapping(src.add(i), dst.add(i), 4); - i += 4; + i = i.debug_strict_add(4); } - if i + 1 < count { + if i.debug_strict_add(1) < count { ptr::copy_nonoverlapping(src.add(i), dst.add(i), 2); - i += 2 + i = i.debug_strict_add(2) } if i < count { *dst.add(i) = *src.add(i); - i += 1; + i = i.debug_strict_add(1); } debug_assert_eq!(i, count); @@ -211,14 +214,14 @@ impl SipHasher128 { debug_assert!(nbuf < BUFFER_SIZE); debug_assert!(nbuf + LEN < BUFFER_WITH_SPILL_SIZE); - if nbuf + LEN < BUFFER_SIZE { + if nbuf.debug_strict_add(LEN) < BUFFER_SIZE { unsafe { // The memcpy call is optimized away because the size is known. let dst = (self.buf.as_mut_ptr() as *mut u8).add(nbuf); ptr::copy_nonoverlapping(bytes.as_ptr(), dst, LEN); } - self.nbuf = nbuf + LEN; + self.nbuf = nbuf.debug_strict_add(LEN); return; } @@ -265,8 +268,9 @@ impl SipHasher128 { // This function should only be called when the write fills the buffer. // Therefore, when LEN == 1, the new `self.nbuf` must be zero. // LEN is statically known, so the branch is optimized away. - self.nbuf = if LEN == 1 { 0 } else { nbuf + LEN - BUFFER_SIZE }; - self.processed += BUFFER_SIZE; + self.nbuf = + if LEN == 1 { 0 } else { nbuf.debug_strict_add(LEN).debug_strict_sub(BUFFER_SIZE) }; + self.processed = self.processed.debug_strict_add(BUFFER_SIZE); } } @@ -277,7 +281,7 @@ impl SipHasher128 { let nbuf = self.nbuf; debug_assert!(nbuf < BUFFER_SIZE); - if nbuf + length < BUFFER_SIZE { + if nbuf.debug_strict_add(length) < BUFFER_SIZE { unsafe { let dst = (self.buf.as_mut_ptr() as *mut u8).add(nbuf); @@ -289,7 +293,7 @@ impl SipHasher128 { } } - self.nbuf = nbuf + length; + self.nbuf = nbuf.debug_strict_add(length); return; } @@ -315,7 +319,7 @@ impl SipHasher128 { // This function should only be called when the write fills the buffer, // so we know that there is enough input to fill the current element. let valid_in_elem = nbuf % ELEM_SIZE; - let needed_in_elem = ELEM_SIZE - valid_in_elem; + let needed_in_elem = ELEM_SIZE.debug_strict_sub(valid_in_elem); let src = msg.as_ptr(); let dst = (self.buf.as_mut_ptr() as *mut u8).add(nbuf); @@ -327,7 +331,7 @@ impl SipHasher128 { // ELEM_SIZE` to show the compiler that this loop's upper bound is > 0. // We know that is true, because last step ensured we have a full // element in the buffer. - let last = nbuf / ELEM_SIZE + 1; + let last = (nbuf / ELEM_SIZE).debug_strict_add(1); for i in 0..last { let elem = self.buf.get_unchecked(i).assume_init().to_le(); @@ -338,7 +342,7 @@ impl SipHasher128 { // Process the remaining element-sized chunks of input. let mut processed = needed_in_elem; - let input_left = length - processed; + let input_left = length.debug_strict_sub(processed); let elems_left = input_left / ELEM_SIZE; let extra_bytes_left = input_left % ELEM_SIZE; @@ -347,7 +351,7 @@ impl SipHasher128 { self.state.v3 ^= elem; Sip13Rounds::c_rounds(&mut self.state); self.state.v0 ^= elem; - processed += ELEM_SIZE; + processed = processed.debug_strict_add(ELEM_SIZE); } // Copy remaining input into start of buffer. @@ -356,7 +360,7 @@ impl SipHasher128 { copy_nonoverlapping_small(src, dst, extra_bytes_left); self.nbuf = extra_bytes_left; - self.processed += nbuf + processed; + self.processed = self.processed.debug_strict_add(nbuf.debug_strict_add(processed)); } } @@ -394,7 +398,7 @@ impl SipHasher128 { }; // Finalize the hash. - let length = self.processed + self.nbuf; + let length = self.processed.debug_strict_add(self.nbuf); let b: u64 = ((length as u64 & 0xff) << 56) | elem; state.v3 ^= b; |
