compiler/rustc_data_structures/src/graph/dominators/mod.rs

   1 //! Finding the dominators in a control-flow graph.
   2 //!
   3 //! Algorithm based on Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy,
   4 //! "A Simple, Fast Dominance Algorithm",
   5 //! Rice Computer Science TS-06-33870,
   6 //! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>.
   7
   8 use super::iterate::reverse_post_order;
   9 use super::ControlFlowGraph;
  10 use rustc_index::vec::{Idx, IndexVec};
  11 use std::cmp::Ordering;
  12
  13 #[cfg(test)]
  14 mod tests;
  15
  16 pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> {
  17     let start_node = graph.start_node();
  18     let rpo = reverse_post_order(&graph, start_node);
  19     dominators_given_rpo(graph, &rpo)
  20 }
  21
  22 fn dominators_given_rpo<G: ControlFlowGraph>(graph: G, rpo: &[G::Node]) -> Dominators<G::Node> {
  23     let start_node = graph.start_node();
  24     assert_eq!(rpo[0], start_node);
  25
  26     // compute the post order index (rank) for each node
  27     let mut post_order_rank = IndexVec::from_elem_n(0, graph.num_nodes());
  28     for (index, node) in rpo.iter().rev().cloned().enumerate() {
  29         post_order_rank[node] = index;
  30     }
  31
  32     let mut immediate_dominators = IndexVec::from_elem_n(None, graph.num_nodes());
  33     immediate_dominators[start_node] = Some(start_node);
  34
  35     let mut changed = true;
  36     while changed {
  37         changed = false;
  38
  39         for &node in &rpo[1..] {
  40             let mut new_idom = None;
  41             for pred in graph.predecessors(node) {
  42                 if immediate_dominators[pred].is_some() {
  43                     // (*) dominators for `pred` have been calculated
  44                     new_idom = Some(if let Some(new_idom) = new_idom {
  45                         intersect(&post_order_rank, &immediate_dominators, new_idom, pred)
  46                     } else {
  47                         pred
  48                     });
  49                 }
  50             }
  51
  52             if new_idom != immediate_dominators[node] {
  53                 immediate_dominators[node] = new_idom;
  54                 changed = true;
  55             }
  56         }
  57     }
  58
  59     Dominators { post_order_rank, immediate_dominators }
  60 }
  61
  62 fn intersect<Node: Idx>(
  63     post_order_rank: &IndexVec<Node, usize>,
  64     immediate_dominators: &IndexVec<Node, Option<Node>>,
  65     mut node1: Node,
  66     mut node2: Node,
  67 ) -> Node {
  68     while node1 != node2 {
  69         while post_order_rank[node1] < post_order_rank[node2] {
  70             node1 = immediate_dominators[node1].unwrap();
  71         }
  72
  73         while post_order_rank[node2] < post_order_rank[node1] {
  74             node2 = immediate_dominators[node2].unwrap();
  75         }
  76     }
  77
  78     node1
  79 }
  80
  81 #[derive(Clone, Debug)]
  82 pub struct Dominators<N: Idx> {
  83     post_order_rank: IndexVec<N, usize>,
  84     immediate_dominators: IndexVec<N, Option<N>>,
  85 }
  86
  87 impl<Node: Idx> Dominators<Node> {
  88     pub fn dummy() -> Self {
  89         Self { post_order_rank: IndexVec::new(), immediate_dominators: IndexVec::new() }
  90     }
  91
  92     pub fn is_reachable(&self, node: Node) -> bool {
  93         self.immediate_dominators[node].is_some()
  94     }
  95
  96     pub fn immediate_dominator(&self, node: Node) -> Node {
  97         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
  98         self.immediate_dominators[node].unwrap()
  99     }
 100
 101     pub fn dominators(&self, node: Node) -> Iter<'_, Node> {
 102         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
 103         Iter { dominators: self, node: Some(node) }
 104     }
 105
 106     pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
 107         // FIXME -- could be optimized by using post-order-rank
 108         self.dominators(node).any(|n| n == dom)
 109     }
 110
 111     /// Provide deterministic ordering of nodes such that, if any two nodes have a dominator
 112     /// relationship, the dominator will always precede the dominated. (The relative ordering
 113     /// of two unrelated nodes will also be consistent, but otherwise the order has no
 114     /// meaning.) This method cannot be used to determine if either Node dominates the other.
 115     pub fn rank_partial_cmp(&self, lhs: Node, rhs: Node) -> Option<Ordering> {
 116         self.post_order_rank[lhs].partial_cmp(&self.post_order_rank[rhs])
 117     }
 118 }
 119
 120 pub struct Iter<'dom, Node: Idx> {
 121     dominators: &'dom Dominators<Node>,
 122     node: Option<Node>,
 123 }
 124
 125 impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
 126     type Item = Node;
 127
 128     fn next(&mut self) -> Option<Self::Item> {
 129         if let Some(node) = self.node {
 130             let dom = self.dominators.immediate_dominator(node);
 131             if dom == node {
 132                 self.node = None; // reached the root
 133             } else {
 134                 self.node = Some(dom);
 135             }
 136             Some(node)
 137         } else {
 138             None
 139         }
 140     }
 141 }