[rustc.git] / src / librustc_data_structures / control_flow_graph / dominators / mod.rs

// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Algorithm citation:
//! A Simple, Fast Dominance Algorithm.
//! Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
//! Rice Computer Science TS-06-33870
//! https://www.cs.rice.edu/~keith/EMBED/dom.pdf

use super::ControlFlowGraph;
use super::iterate::reverse_post_order;
use super::super::indexed_vec::{IndexVec, Idx};

use std::fmt;

#[cfg(test)]
mod test;

pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
    let start_node = graph.start_node();
    let rpo = reverse_post_order(graph, start_node);
    dominators_given_rpo(graph, &rpo)
}

pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
                                                 rpo: &[G::Node])
                                                 -> Dominators<G::Node> {
    let start_node = graph.start_node();
    assert_eq!(rpo[0], start_node);

    // compute the post order index (rank) for each node
    let mut post_order_rank: IndexVec<G::Node, usize> = IndexVec::from_elem_n(usize::default(),
                                                                              graph.num_nodes());
    for (index, node) in rpo.iter().rev().cloned().enumerate() {
        post_order_rank[node] = index;
    }

    let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
        IndexVec::from_elem_n(Option::default(), graph.num_nodes());
    immediate_dominators[start_node] = Some(start_node);

    let mut changed = true;
    while changed {
        changed = false;

        for &node in &rpo[1..] {
            let mut new_idom = None;
            for pred in graph.predecessors(node) {
                if immediate_dominators[pred].is_some() {
                    // (*)
                    // (*) dominators for `pred` have been calculated
                    new_idom = intersect_opt(&post_order_rank,
                                             &immediate_dominators,
                                             new_idom,
                                             Some(pred));
                }
            }

            if new_idom != immediate_dominators[node] {
                immediate_dominators[node] = new_idom;
                changed = true;
            }
        }
    }

    Dominators {
        post_order_rank: post_order_rank,
        immediate_dominators: immediate_dominators,
    }
}

fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
                            immediate_dominators: &IndexVec<Node, Option<Node>>,
                            node1: Option<Node>,
                            node2: Option<Node>)
                            -> Option<Node> {
    match (node1, node2) {
        (None, None) => None,
        (Some(n), None) | (None, Some(n)) => Some(n),
        (Some(n1), Some(n2)) => Some(intersect(post_order_rank, immediate_dominators, n1, n2)),
    }
}

fn intersect<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
                        immediate_dominators: &IndexVec<Node, Option<Node>>,
                        mut node1: Node,
                        mut node2: Node)
                        -> Node {
    while node1 != node2 {
        while post_order_rank[node1] < post_order_rank[node2] {
            node1 = immediate_dominators[node1].unwrap();
        }

        while post_order_rank[node2] < post_order_rank[node1] {
            node2 = immediate_dominators[node2].unwrap();
        }
    }
    return node1;
}

#[derive(Clone, Debug)]
pub struct Dominators<N: Idx> {
    post_order_rank: IndexVec<N, usize>,
    immediate_dominators: IndexVec<N, Option<N>>,
}

impl<Node: Idx> Dominators<Node> {
    pub fn is_reachable(&self, node: Node) -> bool {
        self.immediate_dominators[node].is_some()
    }

    pub fn immediate_dominator(&self, node: Node) -> Node {
        assert!(self.is_reachable(node), "node {:?} is not reachable", node);
        self.immediate_dominators[node].unwrap()
    }

    pub fn dominators(&self, node: Node) -> Iter<Node> {
        assert!(self.is_reachable(node), "node {:?} is not reachable", node);
        Iter {
            dominators: self,
            node: Some(node),
        }
    }

    pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
        // FIXME -- could be optimized by using post-order-rank
        self.dominators(node).any(|n| n == dom)
    }

    pub fn mutual_dominator_node(&self, node1: Node, node2: Node) -> Node {
        assert!(self.is_reachable(node1),
                "node {:?} is not reachable",
                node1);
        assert!(self.is_reachable(node2),
                "node {:?} is not reachable",
                node2);
        intersect::<Node>(&self.post_order_rank,
                          &self.immediate_dominators,
                          node1,
                          node2)
    }

    pub fn mutual_dominator<I>(&self, iter: I) -> Option<Node>
        where I: IntoIterator<Item = Node>
    {
        let mut iter = iter.into_iter();
        iter.next()
            .map(|dom| iter.fold(dom, |dom, node| self.mutual_dominator_node(dom, node)))
    }

    pub fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> {
        &self.immediate_dominators
    }

    pub fn dominator_tree(&self) -> DominatorTree<Node> {
        let elem: Vec<Node> = Vec::new();
        let mut children: IndexVec<Node, Vec<Node>> =
            IndexVec::from_elem_n(elem, self.immediate_dominators.len());
        let mut root = None;
        for (index, immed_dom) in self.immediate_dominators.iter().enumerate() {
            let node = Node::new(index);
            match *immed_dom {
                None => {
                    // node not reachable
                }
                Some(immed_dom) => {
                    if node == immed_dom {
                        root = Some(node);
                    } else {
                        children[immed_dom].push(node);
                    }
                }
            }
        }
        DominatorTree {
            root: root.unwrap(),
            children: children,
        }
    }
}

pub struct Iter<'dom, Node: Idx + 'dom> {
    dominators: &'dom Dominators<Node>,
    node: Option<Node>,
}

impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
    type Item = Node;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(node) = self.node {
            let dom = self.dominators.immediate_dominator(node);
            if dom == node {
                self.node = None; // reached the root
            } else {
                self.node = Some(dom);
            }
            return Some(node);
        } else {
            return None;
        }
    }
}

pub struct DominatorTree<N: Idx> {
    root: N,
    children: IndexVec<N, Vec<N>>,
}

impl<Node: Idx> DominatorTree<Node> {
    pub fn root(&self) -> Node {
        self.root
    }

    pub fn children(&self, node: Node) -> &[Node] {
        &self.children[node]
    }

    pub fn iter_children_of(&self, node: Node) -> IterChildrenOf<Node> {
        IterChildrenOf {
            tree: self,
            stack: vec![node],
        }
    }
}

pub struct IterChildrenOf<'iter, Node: Idx + 'iter> {
    tree: &'iter DominatorTree<Node>,
    stack: Vec<Node>,
}

impl<'iter, Node: Idx> Iterator for IterChildrenOf<'iter, Node> {
    type Item = Node;

    fn next(&mut self) -> Option<Node> {
        if let Some(node) = self.stack.pop() {
            self.stack.extend(self.tree.children(node));
            Some(node)
        } else {
            None
        }
    }
}

impl<Node: Idx> fmt::Debug for DominatorTree<Node> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        fmt::Debug::fmt(&DominatorTreeNode {
                            tree: self,
                            node: self.root,
                        },
                        fmt)
    }
}

struct DominatorTreeNode<'tree, Node: Idx> {
    tree: &'tree DominatorTree<Node>,
    node: Node,
}

impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        let subtrees: Vec<_> = self.tree
            .children(self.node)
            .iter()
            .map(|&child| {
                DominatorTreeNode {
                    tree: self.tree,
                    node: child,
                }
            })
            .collect();
        fmt.debug_tuple("")
            .field(&self.node)
            .field(&subtrees)
            .finish()
    }
}
Commit	Line	Data
3157f602 XL	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,
c30ab7b3 SL	60	&immediate_dominators,
	61	new_idom,
	62	Some(pred));
3157f602 XL	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: post_order_rank,
	75	immediate_dominators: immediate_dominators,
	76	}
	77	}
	78
	79	fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
c30ab7b3 SL	80	immediate_dominators: &IndexVec<Node, Option<Node>>,
	81	node1: Option<Node>,
	82	node2: Option<Node>)
	83	-> Option<Node> {
3157f602 XL	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>,
c30ab7b3 SL	92	immediate_dominators: &IndexVec<Node, Option<Node>>,
	93	mut node1: Node,
	94	mut node2: Node)
	95	-> Node {
3157f602 XL	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	pub fn mutual_dominator_node(&self, node1: Node, node2: Node) -> Node {
	138	assert!(self.is_reachable(node1),
	139	"node {:?} is not reachable",
	140	node1);
	141	assert!(self.is_reachable(node2),
	142	"node {:?} is not reachable",
	143	node2);
	144	intersect::<Node>(&self.post_order_rank,
c30ab7b3 SL	145	&self.immediate_dominators,
	146	node1,
	147	node2)
3157f602 XL	148	}
	149
	150	pub fn mutual_dominator<I>(&self, iter: I) -> Option<Node>
	151	where I: IntoIterator<Item = Node>
	152	{
	153	let mut iter = iter.into_iter();
	154	iter.next()
	155	.map(\|dom\| iter.fold(dom, \|dom, node\| self.mutual_dominator_node(dom, node)))
	156	}
	157
	158	pub fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> {
	159	&self.immediate_dominators
	160	}
	161
	162	pub fn dominator_tree(&self) -> DominatorTree<Node> {
	163	let elem: Vec<Node> = Vec::new();
	164	let mut children: IndexVec<Node, Vec<Node>> =
	165	IndexVec::from_elem_n(elem, self.immediate_dominators.len());
	166	let mut root = None;
	167	for (index, immed_dom) in self.immediate_dominators.iter().enumerate() {
	168	let node = Node::new(index);
	169	match *immed_dom {
	170	None => {
	171	// node not reachable
	172	}
	173	Some(immed_dom) => {
	174	if node == immed_dom {
	175	root = Some(node);
	176	} else {
	177	children[immed_dom].push(node);
	178	}
	179	}
	180	}
	181	}
	182	DominatorTree {
	183	root: root.unwrap(),
	184	children: children,
	185	}
	186	}
	187	}
	188
	189	pub struct Iter<'dom, Node: Idx + 'dom> {
	190	dominators: &'dom Dominators<Node>,
	191	node: Option<Node>,
	192	}
	193
	194	impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
	195	type Item = Node;
	196
	197	fn next(&mut self) -> Option<Self::Item> {
	198	if let Some(node) = self.node {
	199	let dom = self.dominators.immediate_dominator(node);
	200	if dom == node {
	201	self.node = None; // reached the root
	202	} else {
	203	self.node = Some(dom);
	204	}
	205	return Some(node);
	206	} else {
	207	return None;
	208	}
	209	}
	210	}
	211
212	pub struct DominatorTree<N: Idx> {
213	root: N,
214	children: IndexVec<N, Vec<N>>,
215	}
216
217	impl<Node: Idx> DominatorTree<Node> {
218	pub fn root(&self) -> Node {
219	self.root
220	}
221
222	pub fn children(&self, node: Node) -> &[Node] {
223	&self.children[node]
224	}
225
226	pub fn iter_children_of(&self, node: Node) -> IterChildrenOf<Node> {
227	IterChildrenOf {
228	tree: self,
229	stack: vec![node],
230	}
231	}
232	}
233
234	pub struct IterChildrenOf<'iter, Node: Idx + 'iter> {
235	tree: &'iter DominatorTree<Node>,
236	stack: Vec<Node>,
237	}
238
239	impl<'iter, Node: Idx> Iterator for IterChildrenOf<'iter, Node> {
240	type Item = Node;
241
242	fn next(&mut self) -> Option<Node> {
243	if let Some(node) = self.stack.pop() {
244	self.stack.extend(self.tree.children(node));
245	Some(node)
246	} else {
247	None
248	}
249	}
250	}
251
252	impl<Node: Idx> fmt::Debug for DominatorTree<Node> {
253	fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
254	fmt::Debug::fmt(&DominatorTreeNode {
255	tree: self,
256	node: self.root,
257	},
258	fmt)
259	}
260	}
261
262	struct DominatorTreeNode<'tree, Node: Idx> {
263	tree: &'tree DominatorTree<Node>,
264	node: Node,
265	}
266
267	impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
268	fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
269	let subtrees: Vec<_> = self.tree
270	.children(self.node)
271	.iter()
272	.map(\|&child\| {
273	DominatorTreeNode {
274	tree: self.tree,
275	node: child,
276	}
277	})
278	.collect();
279	fmt.debug_tuple("")
280	.field(&self.node)
281	.field(&subtrees)
282	.finish()
283	}
284	}