From 4f9fe856a25ab29345b90e7725509e9ee38a37be Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:41 +0200 Subject: Adding upstream version 1.69.0+dfsg1. Signed-off-by: Daniel Baumann --- .../src/graph/dominators/mod.rs | 51 +++++++++++++++++++++- 1 file changed, 49 insertions(+), 2 deletions(-) (limited to 'compiler/rustc_data_structures/src/graph/dominators') 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(graph: G) -> Dominators { // 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 { 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>, } impl Dominators { + /// 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 Dominators { 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) } -- cgit v1.2.3