src/librustc_data_structures/control_flow_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::ControlFlowGraph;
  18 use super::iterate::reverse_post_order;
  19 use super::super::indexed_vec::{IndexVec, Idx};
  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>(graph: &G,
  33                                                  rpo: &[G::Node])
  34                                                  -> Dominators<G::Node> {
  35     let start_node = graph.start_node();
  36     assert_eq!(rpo[0], start_node);
  37
  38     // compute the post order index (rank) for each node
  39     let mut post_order_rank: IndexVec<G::Node, usize> = IndexVec::from_elem_n(usize::default(),
  40                                                                               graph.num_nodes());
  41     for (index, node) in rpo.iter().rev().cloned().enumerate() {
  42         post_order_rank[node] = index;
  43     }
  44
  45     let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
  46         IndexVec::from_elem_n(Option::default(), graph.num_nodes());
  47     immediate_dominators[start_node] = Some(start_node);
  48
  49     let mut changed = true;
  50     while changed {
  51         changed = false;
  52
  53         for &node in &rpo[1..] {
  54             let mut new_idom = None;
  55             for pred in graph.predecessors(node) {
  56                 if immediate_dominators[pred].is_some() {
  57                     // (*)
  58                     // (*) dominators for `pred` have been calculated
  59                     new_idom = intersect_opt(&post_order_rank,
  60                                              &immediate_dominators,
  61                                              new_idom,
  62                                              Some(pred));
  63                 }
  64             }
  65
  66             if new_idom != immediate_dominators[node] {
  67                 immediate_dominators[node] = new_idom;
  68                 changed = true;
  69             }
  70         }
  71     }
  72
  73     Dominators {
  74         post_order_rank,
  75         immediate_dominators,
  76     }
  77 }
  78
  79 fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
  80                             immediate_dominators: &IndexVec<Node, Option<Node>>,
  81                             node1: Option<Node>,
  82                             node2: Option<Node>)
  83                             -> Option<Node> {
  84     match (node1, node2) {
  85         (None, None) => None,
  86         (Some(n), None) | (None, Some(n)) => Some(n),
  87         (Some(n1), Some(n2)) => Some(intersect(post_order_rank, immediate_dominators, n1, n2)),
  88     }
  89 }
  90
  91 fn intersect<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
  92                         immediate_dominators: &IndexVec<Node, Option<Node>>,
  93                         mut node1: Node,
  94                         mut node2: Node)
  95                         -> Node {
  96     while node1 != node2 {
  97         while post_order_rank[node1] < post_order_rank[node2] {
  98             node1 = immediate_dominators[node1].unwrap();
  99         }
 100
 101         while post_order_rank[node2] < post_order_rank[node1] {
 102             node2 = immediate_dominators[node2].unwrap();
 103         }
 104     }
 105     return node1;
 106 }
 107
 108 #[derive(Clone, Debug)]
 109 pub struct Dominators<N: Idx> {
 110     post_order_rank: IndexVec<N, usize>,
 111     immediate_dominators: IndexVec<N, Option<N>>,
 112 }
 113
 114 impl<Node: Idx> Dominators<Node> {
 115     pub fn is_reachable(&self, node: Node) -> bool {
 116         self.immediate_dominators[node].is_some()
 117     }
 118
 119     pub fn immediate_dominator(&self, node: Node) -> Node {
 120         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
 121         self.immediate_dominators[node].unwrap()
 122     }
 123
 124     pub fn dominators(&self, node: Node) -> Iter<Node> {
 125         assert!(self.is_reachable(node), "node {:?} is not reachable", node);
 126         Iter {
 127             dominators: self,
 128             node: Some(node),
 129         }
 130     }
 131
 132     pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
 133         // FIXME -- could be optimized by using post-order-rank
 134         self.dominators(node).any(|n| n == dom)
 135     }
 136
 137     #[cfg(test)]
 138     fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> {
 139         &self.immediate_dominators
 140     }
 141 }
 142
 143 pub struct Iter<'dom, Node: Idx + 'dom> {
 144     dominators: &'dom Dominators<Node>,
 145     node: Option<Node>,
 146 }
 147
 148 impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
 149     type Item = Node;
 150
 151     fn next(&mut self) -> Option<Self::Item> {
 152         if let Some(node) = self.node {
 153             let dom = self.dominators.immediate_dominator(node);
 154             if dom == node {
 155                 self.node = None; // reached the root
 156             } else {
 157                 self.node = Some(dom);
 158             }
 159             return Some(node);
 160         } else {
 161             return None;
 162         }
 163     }
 164 }
 165
 166 pub struct DominatorTree<N: Idx> {
 167     root: N,
 168     children: IndexVec<N, Vec<N>>,
 169 }
 170
 171 impl<Node: Idx> DominatorTree<Node> {
 172     pub fn children(&self, node: Node) -> &[Node] {
 173         &self.children[node]
 174     }
 175 }
 176
 177 impl<Node: Idx> fmt::Debug for DominatorTree<Node> {
 178     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 179         fmt::Debug::fmt(&DominatorTreeNode {
 180                             tree: self,
 181                             node: self.root,
 182                         },
 183                         fmt)
 184     }
 185 }
 186
 187 struct DominatorTreeNode<'tree, Node: Idx> {
 188     tree: &'tree DominatorTree<Node>,
 189     node: Node,
 190 }
 191
 192 impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
 193     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 194         let subtrees: Vec<_> = self.tree
 195             .children(self.node)
 196             .iter()
 197             .map(|&child| {
 198                 DominatorTreeNode {
 199                     tree: self.tree,
 200                     node: child,
 201                 }
 202             })
 203             .collect();
 204         fmt.debug_tuple("")
 205             .field(&self.node)
 206             .field(&subtrees)
 207             .finish()
 208     }
 209 }