From fa8598cb5066b3463d53682170cc695af2c1b380 Mon Sep 17 00:00:00 2001 From: Camille GILLOT Date: Wed, 17 May 2023 10:37:29 +0000 Subject: Merge DominatorTree and Dominators. --- .../src/graph/dominators/mod.rs | 58 ++++++++++------------ .../src/graph/dominators/tests.rs | 8 +-- 2 files changed, 30 insertions(+), 36 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/graph/dominators/mod.rs b/compiler/rustc_data_structures/src/graph/dominators/mod.rs index 2112b7bcbe3..4868f49d8d5 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -26,7 +26,7 @@ rustc_index::newtype_index! { struct PreorderIndex {} } -pub fn dominator_tree(graph: G) -> DominatorTree { +pub fn dominators(graph: &G) -> Dominators { // compute the post order index (rank) for each node let mut post_order_rank = IndexVec::from_elem_n(0, graph.num_nodes()); @@ -244,7 +244,10 @@ pub fn dominator_tree(graph: G) -> DominatorTree { let start_node = graph.start_node(); immediate_dominators[start_node] = None; - DominatorTree { start_node, post_order_rank, immediate_dominators } + + let time = compute_access_time(start_node, &immediate_dominators); + + Dominators { start_node, post_order_rank, immediate_dominators, time } } /// Evaluate the link-eval virtual forest, providing the currently minimum semi @@ -309,16 +312,17 @@ fn compress( /// Tracks the list of dominators for each node. #[derive(Clone, Debug)] -pub struct DominatorTree { +pub struct Dominators { start_node: N, post_order_rank: IndexVec, // 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>, + time: IndexVec, } -impl DominatorTree { +impl Dominators { /// Returns true if node is reachable from the start node. pub fn is_reachable(&self, node: Node) -> bool { node == self.start_node || self.immediate_dominators[node].is_some() @@ -343,10 +347,22 @@ impl DominatorTree { pub fn rank_partial_cmp(&self, lhs: Node, rhs: Node) -> Option { self.post_order_rank[rhs].partial_cmp(&self.post_order_rank[lhs]) } + + /// Returns true if `a` dominates `b`. + /// + /// # Panics + /// + /// Panics if `b` is unreachable. + pub fn dominates(&self, a: Node, b: Node) -> bool { + let a = self.time[a]; + let b = self.time[b]; + assert!(b.start != 0, "node {b:?} is not reachable"); + a.start <= b.start && b.finish <= a.finish + } } pub struct Iter<'dom, Node: Idx> { - dom_tree: &'dom DominatorTree, + dom_tree: &'dom Dominators, node: Option, } @@ -363,11 +379,6 @@ impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> { } } -#[derive(Clone, Debug)] -pub struct Dominators { - time: IndexVec, -} - /// Describes the number of vertices discovered at the time when processing of a particular vertex /// started and when it finished. Both values are zero for unreachable vertices. #[derive(Copy, Clone, Default, Debug)] @@ -376,27 +387,10 @@ struct Time { finish: u32, } -impl Dominators { - pub fn dummy() -> Self { - Self { time: Default::default() } - } - - /// Returns true if `a` dominates `b`. - /// - /// # Panics - /// - /// Panics if `b` is unreachable. - pub fn dominates(&self, a: Node, b: Node) -> bool { - let a = self.time[a]; - let b = self.time[b]; - assert!(b.start != 0, "node {b:?} is not reachable"); - a.start <= b.start && b.finish <= a.finish - } -} - -pub fn dominators(tree: &DominatorTree) -> Dominators { - let DominatorTree { start_node, ref immediate_dominators, post_order_rank: _ } = *tree; - +fn compute_access_time( + start_node: N, + immediate_dominators: &IndexSlice>, +) -> IndexVec { // Transpose the dominator tree edges, so that child nodes of vertex v are stored in // node[edges[v].start..edges[v].end]. let mut edges: IndexVec> = @@ -446,5 +440,5 @@ pub fn dominators(tree: &DominatorTree) -> Dominators { } } - Dominators { time } + time } diff --git a/compiler/rustc_data_structures/src/graph/dominators/tests.rs b/compiler/rustc_data_structures/src/graph/dominators/tests.rs index 61a21724dda..31531fe3e2a 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/tests.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/tests.rs @@ -6,7 +6,7 @@ use super::super::tests::TestGraph; fn diamond() { let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]); - let tree = dominator_tree(&graph); + let tree = dominators(&graph); let immediate_dominators = &tree.immediate_dominators; assert_eq!(immediate_dominators[0], None); assert_eq!(immediate_dominators[1], Some(0)); @@ -22,7 +22,7 @@ fn paper() { &[(6, 5), (6, 4), (5, 1), (4, 2), (4, 3), (1, 2), (2, 3), (3, 2), (2, 1)], ); - let dom_tree = dominator_tree(&graph); + let dom_tree = dominators(&graph); let immediate_dominators = &dom_tree.immediate_dominators; assert_eq!(immediate_dominators[0], None); // <-- note that 0 is not in graph assert_eq!(immediate_dominators[1], Some(6)); @@ -41,13 +41,13 @@ fn paper_slt() { &[(1, 2), (1, 3), (2, 3), (2, 7), (3, 4), (3, 6), (4, 5), (5, 4), (6, 7), (7, 8), (8, 5)], ); - dominator_tree(&graph); + dominators(&graph); } #[test] fn immediate_dominator() { let graph = TestGraph::new(1, &[(1, 2), (2, 3)]); - let tree = dominator_tree(&graph); + let tree = dominators(&graph); assert_eq!(tree.immediate_dominator(0), None); assert_eq!(tree.immediate_dominator(1), None); assert_eq!(tree.immediate_dominator(2), Some(1)); -- cgit 1.4.1-3-g733a5