From 7f4dd9bb815182a1b60242d82890f9b0b3273c4b Mon Sep 17 00:00:00 2001 From: Zalathar Date: Tue, 22 Oct 2024 13:31:54 +1100 Subject: Move `cmp_in_dominator_order` out of graph dominator computation Dominator-order information is only needed for coverage graphs, and is easy enough to collect by just traversing the graph again. This avoids wasted work when computing graph dominators for any other purpose. --- .../src/graph/dominators/mod.rs | 23 +--------------------- 1 file changed, 1 insertion(+), 22 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 7cb013fdbd8..85b030c1a48 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -9,8 +9,6 @@ //! Thomas Lengauer and Robert Endre Tarjan. //! -use std::cmp::Ordering; - use rustc_index::{Idx, IndexSlice, IndexVec}; use super::ControlFlowGraph; @@ -64,9 +62,6 @@ fn is_small_path_graph(g: &G) -> bool { } fn dominators_impl(graph: &G) -> Inner { - // compute the post order index (rank) for each node - let mut post_order_rank = IndexVec::from_elem_n(0, graph.num_nodes()); - // We allocate capacity for the full set of nodes, because most of the time // most of the nodes *are* reachable. let mut parent: IndexVec = @@ -83,12 +78,10 @@ fn dominators_impl(graph: &G) -> Inner { pre_order_to_real.push(graph.start_node()); parent.push(PreorderIndex::ZERO); // the parent of the root node is the root for now. real_to_pre_order[graph.start_node()] = Some(PreorderIndex::ZERO); - 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 `cmp_in_dominator_order` on the final product) // * Parents for each vertex in the preorder tree // // These are all done here rather than through one of the 'standard' @@ -104,8 +97,6 @@ fn dominators_impl(graph: &G) -> Inner { continue 'recurse; } } - post_order_rank[pre_order_to_real[frame.pre_order_idx]] = post_order_idx; - post_order_idx += 1; stack.pop(); } @@ -282,7 +273,7 @@ fn dominators_impl(graph: &G) -> Inner { let time = compute_access_time(start_node, &immediate_dominators); - Inner { post_order_rank, immediate_dominators, time } + Inner { immediate_dominators, time } } /// Evaluate the link-eval virtual forest, providing the currently minimum semi @@ -348,7 +339,6 @@ fn compress( /// Tracks the list of dominators for each node. #[derive(Clone, Debug)] struct Inner { - 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. @@ -379,17 +369,6 @@ impl Dominators { } } - /// Provide deterministic ordering of nodes such that, if any two nodes have a dominator - /// relationship, the dominator will always precede the dominated. (The relative ordering - /// of two unrelated nodes will also be consistent, but otherwise the order has no - /// meaning.) This method cannot be used to determine if either Node dominates the other. - pub fn cmp_in_dominator_order(&self, lhs: Node, rhs: Node) -> Ordering { - match &self.kind { - Kind::Path => lhs.index().cmp(&rhs.index()), - Kind::General(g) => g.post_order_rank[rhs].cmp(&g.post_order_rank[lhs]), - } - } - /// Returns true if `a` dominates `b`. /// /// # Panics -- cgit 1.4.1-3-g733a5 From 3dfc35214509e969cfeec76380af427881a36aa9 Mon Sep 17 00:00:00 2001 From: Zalathar Date: Thu, 24 Oct 2024 16:59:59 +1100 Subject: Replace an FTP link in comments with an equivalent HTTPS link --- compiler/rustc_data_structures/src/graph/dominators/mod.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (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 85b030c1a48..53ff67f60e3 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -2,7 +2,7 @@ //! //! Algorithm based on Loukas Georgiadis, //! "Linear-Time Algorithms for Dominators and Related Problems", -//! +//! //! //! Additionally useful is the original Lengauer-Tarjan paper on this subject, //! "A Fast Algorithm for Finding Dominators in a Flowgraph" -- cgit 1.4.1-3-g733a5