src/librustc_data_structures/graph/dominators/mod.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Algorithm citation:
  12 //! A Simple, Fast Dominance Algorithm.
  13 //! Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
  14 //! Rice Computer Science TS-06-33870
  15 //! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>
  16
  17 use super::super::indexed_vec::{Idx, IndexVec};
  18 use super::iterate::reverse_post_order;
  19 use super::ControlFlowGraph;
  20
  21 use std::fmt;
  22
  23 #[cfg(test)]
  24 mod test;
  25
  26 pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
  27     let start_node = graph.start_node();
  28     let rpo = reverse_post_order(graph, start_node);
  29     dominators_given_rpo(graph, &rpo)
  30 }
  31
  32 pub fn dominators_given_rpo<G: ControlFlowGraph>(
  33     graph: &G,
  34     rpo: &[G::Node],
  35 ) -> Dominators<G::Node> {
  36     let start_node = graph.start_node();
  37     assert_eq!(rpo[0], start_node);
  38
  39     // compute the post order index (rank) for each node
  40     let mut post_order_rank: IndexVec<G::Node, usize> =
  41         IndexVec::from_elem_n(usize::default(), graph.num_nodes());
  42     for (index, node) in rpo.iter().rev().cloned().enumerate() {
  43         post_order_rank[node] = index;
  44     }
  45
  46     let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
  47         IndexVec::from_elem_n(Option::default(), graph.num_nodes());
  48     immediate_dominators[start_node] = Some(start_node);
  49
  50     let mut changed = true;
  51     while changed {
  52         changed = false;
  53
  54         for &node in &rpo[1..] {
  55             let mut new_idom = None;
  56             for pred in graph.predecessors(node) {
  57                 if immediate_dominators[pred].is_some() {
  58                     // (*)
  59                     // (*) dominators for `pred` have been calculated
  60                     new_idom = intersect_opt(
  61                         &post_order_rank,
  62                         &immediate_dominators,
  63                         new_idom,
  64                         Some(pred),
  65                     );
  66                 }
  67             }
  68
  69             if new_idom != immediate_dominators[node] {
  70                 immediate_dominators[node] = new_idom;
  71                 changed = true;
  72             }
  73         }
  74     }
  75
  76     Dominators {
  77         post_order_rank,
  78         immediate_dominators,
  79     }
  80 }
  81
  82 fn intersect_opt<Node: Idx>(
  83     post_order_rank: &IndexVec<Node, usize>,
  84     immediate_dominators: &IndexVec<Node, Option<Node>>,
  85     node1: Option<Node>,
  86     node2: Option<Node>,
  87 ) -> Option<Node> {
  88     match (node1, node2) {
  89         (None, None) => None,
  90         (Some(n), None) | (None, Some(n)) => Some(n),
  91         (Some(n1), Some(n2)) => Some(intersect(post_order_rank, immediate_dominators, n1, n2)),
  92     }
  93 }
  94
  95 fn intersect<Node: Idx>(
  96     post_order_rank: &IndexVec<Node, usize>,
  97     immediate_dominators: &IndexVec<Node, Option<Node>>,
  98     mut node1: Node,
  99     mut node2: Node,
 100 ) -> Node {
 101     while node1 != node2 {
 102         while post_order_rank[node1] < post_order_rank[node2] {
 103             node1 = immediate_dominators[node1].unwrap();
 104         }
 105
 106         while post_order_rank[node2] < post_order_rank[node1] {
 107             node2 = immediate_dominators[node2].unwrap();
 108         }
 109     }
 110
 111     node1
 112 }
 113
 114 #[derive(Clone, Debug)]
 115 pub struct Dominators<N: Idx> {
 116     post_order_rank: IndexVec<N, usize>,
 117     immediate_dominators: IndexVec<N, Option<N>>,
 118 }
 119
 120 impl<Node: Idx> Dominators<Node> {
 121     pub fn is_reachable(&self, node: Node) -> bool {
 122         self.immediate_dominators[node].is_some()
 123     }
 124
 125     pub fn immediate_dominator(&self, node: Node) -> Node {
 126         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
 127         self.immediate_dominators[node].unwrap()
 128     }
 129
 130     pub fn dominators(&self, node: Node) -> Iter<Node> {
 131         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
 132         Iter {
 133             dominators: self,
 134             node: Some(node),
 135         }
 136     }
 137
 138     pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
 139         // FIXME -- could be optimized by using post-order-rank
 140         self.dominators(node).any(|n| n == dom)
 141     }
 142
 143     #[cfg(test)]
 144     fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> {
 145         &self.immediate_dominators
 146     }
 147 }
 148
 149 pub struct Iter<'dom, Node: Idx + 'dom> {
 150     dominators: &'dom Dominators<Node>,
 151     node: Option<Node>,
 152 }
 153
 154 impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
 155     type Item = Node;
 156
 157     fn next(&mut self) -> Option<Self::Item> {
 158         if let Some(node) = self.node {
 159             let dom = self.dominators.immediate_dominator(node);
 160             if dom == node {
 161                 self.node = None; // reached the root
 162             } else {
 163                 self.node = Some(dom);
 164             }
 165             return Some(node);
 166         } else {
 167             return None;
 168         }
 169     }
 170 }
 171
 172 pub struct DominatorTree<N: Idx> {
 173     root: N,
 174     children: IndexVec<N, Vec<N>>,
 175 }
 176
 177 impl<Node: Idx> DominatorTree<Node> {
 178     pub fn children(&self, node: Node) -> &[Node] {
 179         &self.children[node]
 180     }
 181 }
 182
 183 impl<Node: Idx> fmt::Debug for DominatorTree<Node> {
 184     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 185         fmt::Debug::fmt(
 186             &DominatorTreeNode {
 187                 tree: self,
 188                 node: self.root,
 189             },
 190             fmt,
 191         )
 192     }
 193 }
 194
 195 struct DominatorTreeNode<'tree, Node: Idx> {
 196     tree: &'tree DominatorTree<Node>,
 197     node: Node,
 198 }
 199
 200 impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
 201     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 202         let subtrees: Vec<_> = self.tree
 203             .children(self.node)
 204             .iter()
 205             .map(|&child| DominatorTreeNode {
 206                 tree: self.tree,
 207                 node: child,
 208             })
 209             .collect();
 210         fmt.debug_tuple("")
 211             .field(&self.node)
 212             .field(&subtrees)
 213             .finish()
 214     }
 215 }