src/librustc_data_structures/graph/dominators/mod.rs

   1 //! Algorithm citation:
   2 //! A Simple, Fast Dominance Algorithm.
   3 //! Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
   4 //! Rice Computer Science TS-06-33870
   5 //! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>
   6
   7 use super::iterate::reverse_post_order;
   8 use super::ControlFlowGraph;
   9 use rustc_index::vec::{Idx, IndexVec};
  10 use std::borrow::BorrowMut;
  11
  12 #[cfg(test)]
  13 mod tests;
  14
  15 pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> {
  16     let start_node = graph.start_node();
  17     let rpo = reverse_post_order(&graph, start_node);
  18     dominators_given_rpo(graph, &rpo)
  19 }
  20
  21 fn dominators_given_rpo<G: ControlFlowGraph + BorrowMut<G>>(
  22     mut graph: G,
  23     rpo: &[G::Node],
  24 ) -> Dominators<G::Node> {
  25     let start_node = graph.borrow().start_node();
  26     assert_eq!(rpo[0], start_node);
  27
  28     // compute the post order index (rank) for each node
  29     let mut post_order_rank: IndexVec<G::Node, usize> =
  30         (0..graph.borrow().num_nodes()).map(|_| 0).collect();
  31     for (index, node) in rpo.iter().rev().cloned().enumerate() {
  32         post_order_rank[node] = index;
  33     }
  34
  35     let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
  36         (0..graph.borrow().num_nodes()).map(|_| None).collect();
  37     immediate_dominators[start_node] = Some(start_node);
  38
  39     let mut changed = true;
  40     while changed {
  41         changed = false;
  42
  43         for &node in &rpo[1..] {
  44             let mut new_idom = None;
  45             for pred in graph.borrow_mut().predecessors(node) {
  46                 if immediate_dominators[pred].is_some() {
  47                     // (*) dominators for `pred` have been calculated
  48                     new_idom = Some(if let Some(new_idom) = new_idom {
  49                         intersect(&post_order_rank, &immediate_dominators, new_idom, pred)
  50                     } else {
  51                         pred
  52                     });
  53                 }
  54             }
  55
  56             if new_idom != immediate_dominators[node] {
  57                 immediate_dominators[node] = new_idom;
  58                 changed = true;
  59             }
  60         }
  61     }
  62
  63     Dominators { post_order_rank, immediate_dominators }
  64 }
  65
  66 fn intersect<Node: Idx>(
  67     post_order_rank: &IndexVec<Node, usize>,
  68     immediate_dominators: &IndexVec<Node, Option<Node>>,
  69     mut node1: Node,
  70     mut node2: Node,
  71 ) -> Node {
  72     while node1 != node2 {
  73         while post_order_rank[node1] < post_order_rank[node2] {
  74             node1 = immediate_dominators[node1].unwrap();
  75         }
  76
  77         while post_order_rank[node2] < post_order_rank[node1] {
  78             node2 = immediate_dominators[node2].unwrap();
  79         }
  80     }
  81
  82     node1
  83 }
  84
  85 #[derive(Clone, Debug)]
  86 pub struct Dominators<N: Idx> {
  87     post_order_rank: IndexVec<N, usize>,
  88     immediate_dominators: IndexVec<N, Option<N>>,
  89 }
  90
  91 impl<Node: Idx> Dominators<Node> {
  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
 112 pub struct Iter<'dom, Node: Idx> {
 113     dominators: &'dom Dominators<Node>,
 114     node: Option<Node>,
 115 }
 116
 117 impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
 118     type Item = Node;
 119
 120     fn next(&mut self) -> Option<Self::Item> {
 121         if let Some(node) = self.node {
 122             let dom = self.dominators.immediate_dominator(node);
 123             if dom == node {
 124                 self.node = None; // reached the root
 125             } else {
 126                 self.node = Some(dom);
 127             }
 128             Some(node)
 129         } else {
 130             None
 131         }
 132     }
 133 }