open_vaf/analysis/
post_dominance.rs

1//  * ******************************************************************************************
2//  * Copyright (c) 2019 Pascal Kuthe. This file is part of the OpenVAF project.
3//  * It is subject to the license terms in the LICENSE file found in the top-level directory
4//  *  of this distribution and at  https://gitlab.com/DSPOM/OpenVAF/blob/master/LICENSE.
5//  *  No part of OpenVAF, including this file, may be copied, modified, propagated, or
6//  *  distributed except according to the terms contained in the LICENSE file.
7//  * *******************************************************************************************
8
9use crate::cfg::BasicBlockId;
10use crate::ControlFlowGraph;
11use index_vec::*;
12use log::*;
13use std::cmp::Ordering;
14
15pub type IPDOM = IndexVec<BasicBlockId, BasicBlockId>;
16id_type!(PostorderId(u16));
17
18impl ControlFlowGraph {
19    /// An implementation of the simple fast algorithm by [\[Keith 2006\]](https://www.cs.rice.edu/~keith/EMBED/dom.pdf).
20    /// It is adobted for post dominance (simply the dominance of the reverse cfg).
21    /// **returns** - immediate Post_dominator for every cfg node (`ipdom(n)`)
22    pub fn post_dominators(&self) -> IPDOM {
23        let post_order: IndexVec<PostorderId, _> = self.postorder_iter().collect();
24
25        let undefined = post_order.len_idx();
26
27        // Map cfg ids to postorder ids
28        let mut post_order_mapping: IndexVec<BasicBlockId, PostorderId> =
29            index_vec![undefined;post_order.len()];
30        for (pid, (bid, _)) in post_order.iter_enumerated() {
31            post_order_mapping[*bid] = pid;
32        }
33
34        // this idx con not appear
35        let mut ipdom = index_vec![undefined; post_order.len()];
36
37        // last node only post dominates itself
38        ipdom[PostorderId::from_usize(0)] = PostorderId::from_usize(0);
39
40        // TOOD integrate into DFA framework?
41        let mut changed = true;
42        while changed {
43            changed = false;
44
45            // Iterate in post order
46            let mut iter = post_order.iter_enumerated();
47            // Skip the end (root)
48            iter.next();
49
50            for (pid, (bid, bb)) in iter {
51                debug_assert!(*bid != self.end());
52
53                trace!("Simple fast postdominators: iterating {:?}", bid);
54
55                let mut sucessors = bb
56                    .successors()
57                    .map(|bid| post_order_mapping[bid])
58                    .filter(|&p| ipdom[p] != undefined);
59
60                if let Some(new_idom_idx) = sucessors.next() {
61                    let new_idom_idx =
62                        sucessors.fold(new_idom_idx, |new_idom_idx, predecessor_idx| {
63                            intersect(&ipdom, new_idom_idx, predecessor_idx)
64                        });
65                    if new_idom_idx != ipdom[pid] {
66                        trace!("Simple fast postdomiantors: changed {:?}", bid);
67                        ipdom[pid] = new_idom_idx;
68                        changed = true;
69                    }
70                } else {
71                    debug!("No predecessor of {:?} has ben processed yet", bid);
72                    changed = true;
73                }
74            }
75        }
76
77        // Map PostorderIds back to Cfg ids
78        let mut res: IndexVec<BasicBlockId, BasicBlockId> = index_vec![self.start();ipdom.len()];
79        for (pid, &dominator_pid) in ipdom.iter_enumerated() {
80            res[post_order[pid].0] = post_order[dominator_pid].0;
81        }
82
83        res
84    }
85}
86
87fn intersect(
88    post_dominators: &IndexVec<PostorderId, PostorderId>,
89    mut finger1: PostorderId,
90    mut finger2: PostorderId,
91) -> PostorderId {
92    loop {
93        match finger1.cmp(&finger2) {
94            Ordering::Greater => finger1 = post_dominators[finger1],
95            Ordering::Less => finger2 = post_dominators[finger2],
96            Ordering::Equal => return finger1,
97        }
98        trace!("itersection {:?} {:?}", finger1, finger2);
99    }
100}
101
102#[cfg(feature = "graph_debug")]
103mod print {
104    use crate::analysis::IPDOM;
105    use crate::cfg::BasicBlockId;
106    use crate::ControlFlowGraph;
107    use rustc_ap_graphviz as dot;
108    use rustc_ap_graphviz::{Edges, Id, LabelText, Nodes};
109    use std::borrow::Cow;
110    use std::io::Write;
111
112    pub struct IPDOM_TREE<'lt>(&'lt ControlFlowGraph, &'lt IPDOM);
113
114    impl ControlFlowGraph {
115        pub fn render_post_dominators<W: Write>(&self, write: &mut W, ipdom: &IPDOM) {
116            dot::render(&IPDOM_TREE(self, ipdom), write).expect("Rendering failed")
117        }
118    }
119
120    impl<'a> dot::Labeller<'a> for IPDOM_TREE<'a> {
121        type Node = BasicBlockId;
122        type Edge = (BasicBlockId, BasicBlockId);
123
124        fn graph_id(&'a self) -> Id<'a> {
125            dot::Id::new("PostDominatorTree").unwrap()
126        }
127
128        fn node_id(&'a self, id: &Self::Node) -> Id<'a> {
129            dot::Id::new(format!("BB_{}", id)).unwrap()
130        }
131
132        fn node_label(&'a self, &n: &Self::Node) -> LabelText<'a> {
133            LabelText::LabelStr(Cow::Owned(format!("{:?}", n)))
134        }
135        fn edge_label(&'a self, &(start, dst): &(BasicBlockId, BasicBlockId)) -> LabelText<'a> {
136            LabelText::LabelStr(Cow::Borrowed("post dominates"))
137        }
138    }
139
140    impl<'a> dot::GraphWalk<'a> for IPDOM_TREE<'a> {
141        type Node = BasicBlockId;
142        type Edge = (BasicBlockId, BasicBlockId);
143
144        fn nodes(&'a self) -> Nodes<'a, Self::Node> {
145            Cow::Owned(self.0.blocks.indices().collect())
146        }
147
148        fn edges(&'a self) -> Edges<'a, Self::Edge> {
149            Cow::Owned(
150                self.1
151                    .iter_enumerated()
152                    .map(|(ipdom_n, &n)| (n, ipdom_n))
153                    .collect(),
154            )
155        }
156
157        fn source(&'a self, edge: &Self::Edge) -> Self::Node {
158            edge.0
159        }
160
161        fn target(&'a self, edge: &Self::Edge) -> Self::Node {
162            edge.1
163        }
164    }
165}
open_vaf/analysis/post_dominance.rs

open_vaf/analysis/
post_dominance.rs
