From f9982ea24a55a1912198bc49578f7af090e487e9 Mon Sep 17 00:00:00 2001 From: Bryan Garza <1396101+bryangarza@users.noreply.github.com> Date: Fri, 6 Jan 2023 16:26:56 +0000 Subject: Add comment on cause of panic in dominators algorithm --- .../src/graph/dominators/mod.rs | 42 +++++++++++++++++++++- 1 file changed, 41 insertions(+), 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 6398a501983..38a687af7e6 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 }; -- cgit 1.4.1-3-g733a5 From 1bbd655888ec50220e6cd34e846c816c1cad8f17 Mon Sep 17 00:00:00 2001 From: Bryan Garza <1396101+bryangarza@users.noreply.github.com> Date: Fri, 6 Jan 2023 22:04:25 +0000 Subject: Improve efficiency of has_back_edge(...) --- .../src/graph/dominators/mod.rs | 7 +++++++ compiler/rustc_mir_transform/src/ctfe_limit.rs | 21 +++++++++++---------- 2 files changed, 18 insertions(+), 10 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 38a687af7e6..0a21a4249c8 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -304,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() } @@ -320,6 +325,8 @@ 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) } diff --git a/compiler/rustc_mir_transform/src/ctfe_limit.rs b/compiler/rustc_mir_transform/src/ctfe_limit.rs index 76db4a09d91..7d127032179 100644 --- a/compiler/rustc_mir_transform/src/ctfe_limit.rs +++ b/compiler/rustc_mir_transform/src/ctfe_limit.rs @@ -2,8 +2,9 @@ //! (thus indicating there is a loop in the CFG), or whose terminator is a function call. use crate::MirPass; +use rustc_data_structures::graph::dominators::Dominators; use rustc_middle::mir::{ - BasicBlock, BasicBlockData, BasicBlocks, Body, Statement, StatementKind, TerminatorKind, + BasicBlock, BasicBlockData, Body, Statement, StatementKind, TerminatorKind, }; use rustc_middle::ty::TyCtxt; @@ -12,13 +13,14 @@ pub struct CtfeLimit; impl<'tcx> MirPass<'tcx> for CtfeLimit { #[instrument(skip(self, _tcx, body))] fn run_pass(&self, _tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { + let doms = body.basic_blocks.dominators(); let indices: Vec = body .basic_blocks .iter_enumerated() .filter_map(|(node, node_data)| { if matches!(node_data.terminator().kind, TerminatorKind::Call { .. }) // Back edges in a CFG indicate loops - || has_back_edge(&body.basic_blocks, node, &node_data) + || has_back_edge(&doms, node, &node_data) { Some(node) } else { @@ -37,17 +39,16 @@ impl<'tcx> MirPass<'tcx> for CtfeLimit { } fn has_back_edge( - basic_blocks: &BasicBlocks<'_>, + doms: &Dominators, node: BasicBlock, node_data: &BasicBlockData<'_>, ) -> bool { - let doms = basic_blocks.dominators(); - basic_blocks.indices().any(|potential_dom| { - doms.is_reachable(potential_dom) - && doms.is_reachable(node) - && doms.is_dominated_by(node, potential_dom) - && node_data.terminator().successors().into_iter().any(|succ| succ == potential_dom) - }) + if !doms.is_reachable(node) { + return false; + } + // Check if any of the dominators of the node are also the node's successor. + doms.dominators(node) + .any(|dom| node_data.terminator().successors().into_iter().any(|succ| succ == dom)) } fn insert_counter(basic_block_data: &mut BasicBlockData<'_>) { -- cgit 1.4.1-3-g733a5