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::borrow::BorrowMut;
  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 + BorrowMut<G>>(
  23     mut graph: G,
  24     rpo: &[G::Node],
  25 ) -> Dominators<G::Node> {
  26     let start_node = graph.borrow().start_node();
  27     assert_eq!(rpo[0], start_node);
  28
  29     // compute the post order index (rank) for each node
  30     let mut post_order_rank: IndexVec<G::Node, usize> =
  31         (0..graph.borrow().num_nodes()).map(|_| 0).collect();
  32     for (index, node) in rpo.iter().rev().cloned().enumerate() {
  33         post_order_rank[node] = index;
  34     }
  35
  36     let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
  37         (0..graph.borrow().num_nodes()).map(|_| None).collect();
  38     immediate_dominators[start_node] = Some(start_node);
  39
  40     let mut changed = true;
  41     while changed {
  42         changed = false;
  43
  44         for &node in &rpo[1..] {
  45             let mut new_idom = None;
  46             for pred in graph.borrow_mut().predecessors(node) {
  47                 if immediate_dominators[pred].is_some() {
  48                     // (*) dominators for `pred` have been calculated
  49                     new_idom = Some(if let Some(new_idom) = new_idom {
  50                         intersect(&post_order_rank, &immediate_dominators, new_idom, pred)
  51                     } else {
  52                         pred
  53                     });
  54                 }
  55             }
  56
  57             if new_idom != immediate_dominators[node] {
  58                 immediate_dominators[node] = new_idom;
  59                 changed = true;
  60             }
  61         }
  62     }
  63
  64     Dominators { post_order_rank, immediate_dominators }
  65 }
  66
  67 fn intersect<Node: Idx>(
  68     post_order_rank: &IndexVec<Node, usize>,
  69     immediate_dominators: &IndexVec<Node, Option<Node>>,
  70     mut node1: Node,
  71     mut node2: Node,
  72 ) -> Node {
  73     while node1 != node2 {
  74         while post_order_rank[node1] < post_order_rank[node2] {
  75             node1 = immediate_dominators[node1].unwrap();
  76         }
  77
  78         while post_order_rank[node2] < post_order_rank[node1] {
  79             node2 = immediate_dominators[node2].unwrap();
  80         }
  81     }
  82
  83     node1
  84 }
  85
  86 #[derive(Clone, Debug)]
  87 pub struct Dominators<N: Idx> {
  88     post_order_rank: IndexVec<N, usize>,
  89     immediate_dominators: IndexVec<N, Option<N>>,
  90 }
  91
  92 impl<Node: Idx> Dominators<Node> {
  93     pub fn is_reachable(&self, node: Node) -> bool {
  94         self.immediate_dominators[node].is_some()
  95     }
  96
  97     pub fn immediate_dominator(&self, node: Node) -> Node {
  98         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
  99         self.immediate_dominators[node].unwrap()
 100     }
 101
 102     pub fn dominators(&self, node: Node) -> Iter<'_, Node> {
 103         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
 104         Iter { dominators: self, node: Some(node) }
 105     }
 106
 107     pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
 108         // FIXME -- could be optimized by using post-order-rank
 109         self.dominators(node).any(|n| n == dom)
 110     }
 111 }
 112
 113 pub struct Iter<'dom, Node: Idx> {
 114     dominators: &'dom Dominators<Node>,
 115     node: Option<Node>,
 116 }
 117
 118 impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
 119     type Item = Node;
 120
 121     fn next(&mut self) -> Option<Self::Item> {
 122         if let Some(node) = self.node {
 123             let dom = self.dominators.immediate_dominator(node);
 124             if dom == node {
 125                 self.node = None; // reached the root
 126             } else {
 127                 self.node = Some(dom);
 128             }
 129             Some(node)
 130         } else {
 131             None
 132         }
 133     }
 134 }