open_vaf/analysis/
control_dependence.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::analysis::IPDOM;
10use crate::cfg::Terminator;
11use crate::data_structures::BitSet;
12use crate::ir::cfg::BasicBlockId;
13use crate::ControlFlowGraph;
14use index_vec::*;
15use log::*;
16
17pub type ControlDependenceGraph = IndexVec<BasicBlockId, BitSet<BasicBlockId>>;
18
19impl ControlFlowGraph {
20    /// Calculates the Control Dependence Graph of a CFG.
21    /// A basic block is control dependent on a statement if this statements decides whether the block is executed (for example an if statement).
22    /// Statements that cause control flow are not represented as statements but as basic block terminators in the cfg.
23    /// As such the control dependence Graph simply maps basic blocks to all basics block whos terminator affats whether a statements is executed
24    pub fn control_dependence_graph(&self) -> ControlDependenceGraph {
25        self.control_dependence_graph_from_ipdom(&self.post_dominators())
26    }
27
28    /// The backend for [`control_dependence_graph`] which can be used when `ipdom(bb` has already been calcualted to avoid recalculation
29    pub fn control_dependence_graph_from_ipdom(&self, ipdom: &IPDOM) -> ControlDependenceGraph {
30        let mut cdg = index_vec![BitSet::new_empty(self.blocks.len_idx());self.blocks.len()];
31        for (id, bb) in self.blocks.iter_enumerated() {
32            // we only care about control dependencies on branches since end and goto are unconditional jumps
33            if let Terminator::Split {
34                true_block,
35                false_block,
36                merge,
37                ..
38            } = bb.terminator
39            {
40                self.propagate_control_dependence(&mut cdg, &ipdom, true_block, id);
41                if merge != id {
42                    self.propagate_control_dependence(&mut cdg, &ipdom, false_block, id);
43                }
44            }
45        }
46
47        cdg
48    }
49
50    fn propagate_control_dependence(
51        &self,
52        cdg: &mut ControlDependenceGraph,
53        ipdom: &IPDOM,
54        mut from: BasicBlockId,
55        to: BasicBlockId,
56    ) {
57        loop {
58            trace!(
59                "propgating control dependency on {:?} to {:?} until {:?}",
60                to,
61                from,
62                ipdom[to]
63            );
64
65            cdg[from].insert(to);
66            from = ipdom[from];
67            if from == ipdom[to] {
68                break;
69            }
70        }
71    }
72}
73
74#[cfg(feature = "graph_debug")]
75mod print {
76
77    use super::*;
78    use rustc_ap_graphviz as dot;
79    use rustc_ap_graphviz::LabelText::{EscStr, LabelStr};
80    use rustc_ap_graphviz::{Edges, GraphWalk, Id, LabelText, Labeller, Nodes};
81    use std::borrow::Cow;
82    use std::io::Write;
83
84    impl ControlFlowGraph {
85        pub fn render_control_dependence_to<W: Write>(
86            &self,
87            write: &mut W,
88            cdg: &ControlDependenceGraph,
89        ) {
90            dot::render(&ControlDependenceCFG(self, cdg), write).expect("Rendering failed")
91        }
92    }
93
94    struct ControlDependenceCFG<'lt>(&'lt ControlFlowGraph, &'lt ControlDependenceGraph);
95    #[derive(Copy, Clone, Eq, PartialEq)]
96    enum FlowOrDependence {
97        Flow,
98        Dependence,
99    }
100
101    impl<'a> dot::Labeller<'a> for ControlDependenceCFG<'a> {
102        type Node = BasicBlockId;
103        type Edge = (FlowOrDependence, BasicBlockId, BasicBlockId);
104
105        fn graph_id(&'a self) -> Id<'a> {
106            dot::Id::new("ControlFlowGraph").unwrap()
107        }
108
109        fn node_id(&'a self, n: &Self::Node) -> Id<'a> {
110            dot::Id::new(format!("BB_{}", n.index())).unwrap()
111        }
112
113        fn node_label(&'a self, &n: &Self::Node) -> LabelText<'a> {
114            match self.0.blocks[n].terminator {
115                Terminator::End => EscStr(Cow::Owned(format!(
116                    "BB_{}: {} Statements\n END",
117                    n.index(),
118                    self.0.blocks[n].statements.len(),
119                ))),
120                Terminator::Goto(_) => LabelStr(Cow::Owned(format!(
121                    "BB_{}: {} Statements",
122                    n.index(),
123                    self.0.blocks[n].statements.len(),
124                ))),
125                Terminator::Split {
126                    condition, merge, ..
127                } => LabelStr(Cow::Owned(format!(
128                    "BB_{}: {} Statements\nSplit at {:?}\nMerge at BB_{}",
129                    n.index(),
130                    self.0.blocks[n].statements.len(),
131                    condition,
132                    merge.index(),
133                ))),
134            }
135        }
136        fn edge_label(
137            &'a self,
138            &(edge_type, start, dst): &(FlowOrDependence, BasicBlockId, BasicBlockId),
139        ) -> LabelText<'a> {
140            match edge_type {
141                FlowOrDependence::Flow => match self.0[start].terminator {
142                    Terminator::Goto(_) => LabelStr(Cow::Borrowed("GOTO")),
143                    Terminator::End => LabelStr(Cow::Borrowed("ILLEGAL")),
144                    Terminator::Split {
145                        condition,
146                        true_block,
147                        false_block,
148                        merge,
149                    } => {
150                        let true_or_false = if true_block == dst {
151                            "TRUE"
152                        } else if false_block == dst {
153                            "FALSE"
154                        } else {
155                            "ILLEGAL"
156                        };
157                        LabelStr(Cow::Borrowed(true_or_false))
158                    }
159                },
160
161                FlowOrDependence::Dependence => LabelStr(Cow::Borrowed("Control dependence")),
162            }
163        }
164    }
165
166    impl<'a> dot::GraphWalk<'a> for ControlDependenceCFG<'a> {
167        type Node = BasicBlockId;
168        type Edge = (FlowOrDependence, BasicBlockId, BasicBlockId);
169
170        fn nodes(&'a self) -> Nodes<'a, Self::Node> {
171            Cow::Owned(self.0.blocks.indices().collect())
172        }
173
174        fn edges(&'a self) -> Edges<'a, Self::Edge> {
175            let mut edges = Vec::new();
176            for (id, bb) in self.0.blocks.iter_enumerated() {
177                match bb.terminator {
178                    Terminator::Goto(dst) => edges.push((FlowOrDependence::Flow, id, dst)),
179                    Terminator::Split {
180                        condition,
181                        true_block,
182                        false_block,
183                        merge,
184                    } => {
185                        edges.push((FlowOrDependence::Flow, id, false_block));
186                        edges.push((FlowOrDependence::Flow, id, true_block));
187                    }
188                    Terminator::End => (),
189                }
190            }
191            for (src, control_dependencies) in self.1.iter_enumerated() {
192                for dst in control_dependencies.ones() {
193                    edges.push((FlowOrDependence::Dependence, src, dst));
194                }
195            }
196            Cow::Owned(edges)
197        }
198
199        fn source(&'a self, edge: &Self::Edge) -> Self::Node {
200            edge.1
201        }
202
203        fn target(&'a self, edge: &Self::Edge) -> Self::Node {
204            edge.2
205        }
206    }
207}
open_vaf/analysis/control_dependence.rs

open_vaf/analysis/
control_dependence.rs
