open_vaf/analysis/data_flow/
reaching_variables.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#![allow(clippy::similar_names)]
9
10use crate::analysis::data_flow::framework::{
11    DataFlowGraph, Engine, Forward, GenKillAnalysis, GenKillEngine, GenKillSet,
12};
13use crate::analysis::DependencyHandler;
14
15use crate::cfg::*;
16use crate::data_structures::BitSet;
17use crate::ir::hir::DisciplineAccess;
18use crate::ir::{
19    BranchId, ParameterId, PortId, RealExpressionId, StatementId, StringExpressionId,
20    SystemFunctionCall, VariableId,
21};
22use crate::mir::Mir;
23use crate::mir::Statement;
24use crate::ControlFlowGraph;
25use index_vec::*;
26
27#[derive(Debug, Clone)]
28pub struct UseDefGraph {
29    pub stmt_use_def_chains: IndexVec<StatementId, BitSet<StatementId>>,
30    pub terminator_use_def_chains: IndexVec<BasicBlockId, BitSet<StatementId>>,
31    pub assignments: IndexVec<VariableId, BitSet<StatementId>>,
32}
33
34impl UseDefGraph {
35    pub fn new(mir: &Mir, cfg: &ControlFlowGraph) -> Self {
36        let statement_count = mir.statements.len();
37        let var_count = mir.variables.len();
38
39        Self {
40            stmt_use_def_chains: index_vec![BitSet::new_empty(statement_count.into());statement_count],
41            terminator_use_def_chains: index_vec![BitSet::new_empty(statement_count.into());cfg.blocks.len()],
42            assignments: index_vec![BitSet::new_empty(statement_count.into());var_count],
43        }
44    }
45
46    pub fn stmt_count(&self) -> u32 {
47        self.stmt_use_def_chains.len() as u32
48    }
49
50    pub fn len_stmd_idx(&self) -> StatementId {
51        self.stmt_use_def_chains.len_idx()
52    }
53}
54
55pub struct ReachableDefinitionsAnalysis<'lt> {
56    graph: UseDefGraph,
57    mir: &'lt Mir,
58}
59
60impl<'lt> ReachableDefinitionsAnalysis<'lt> {
61    pub fn new(mir: &'lt Mir, cfg: &ControlFlowGraph) -> Self {
62        let mut graph = UseDefGraph::new(mir, cfg);
63
64        for (id, stmt) in mir.statements.iter_enumerated() {
65            match stmt {
66                Statement::Assignment(_, var, _) => graph.assignments[*var].insert(id),
67
68                Statement::Contribute(_, _, _, _) => (),
69            }
70        }
71
72        Self { graph, mir }
73    }
74
75    pub fn run(mut self, cfg: &ControlFlowGraph) -> (UseDefGraph, DataFlowGraph<StatementId>) {
76        let mut genkill_engine = GenKillEngine::new(cfg, &mut self);
77        let engine = Engine::new(cfg, &mut genkill_engine);
78        let dfg = engine.iterate_to_fixpoint();
79
80        let mut reachable = BitSet::new_empty(self.graph.stmt_use_def_chains.len_idx());
81
82        for (id, bb) in cfg.blocks.iter_enumerated() {
83            reachable.union_with(&dfg.in_sets[id]);
84            for stmt in bb.statements.iter().copied() {
85
86
87                match self.mir[stmt] {
88                    Statement::Assignment(_, var, expr) => {
89                        self.mir.track_expression(
90                            expr,
91                            &mut UseDefBuilder {
92                                graph: &mut self.graph,
93                                use_stmt: stmt,
94                            },
95                        );
96
97                        self.graph.stmt_use_def_chains[stmt].intersect_with(&reachable);
98
99                        reachable.difference_with(&self.graph.assignments[var]);
100                        reachable.insert(stmt);
101                    }
102
103                    Statement::Contribute(_, _, _, val) => {
104                        self.mir.track_real_expression(
105                            val,
106                            &mut UseDefBuilder {
107                                graph: &mut self.graph,
108                                use_stmt: stmt,
109                            },
110                        );
111                        self.graph.stmt_use_def_chains[stmt].intersect_with(&reachable);
112
113                        // branches are currently not tracked
114                    }
115                }
116            }
117
118            if let Terminator::Split { condition, .. } = bb.terminator {
119                self.graph.terminator_use_def_chains[id]
120                    .grow(self.graph.stmt_use_def_chains.len_idx());
121
122                self.mir.track_integer_expression(
123                    condition,
124                    &mut UseDefTerminatorBuilder {
125                        graph: &mut self.graph,
126                        use_terminator_block: id,
127                    },
128                );
129
130                self.graph.terminator_use_def_chains[id].intersect_with(&reachable);
131            }
132
133            reachable.clear();
134        }
135
136        (self.graph, dfg)
137    }
138}
139
140impl<'lt> GenKillAnalysis<'_> for ReachableDefinitionsAnalysis<'lt> {
141    type SetType = StatementId;
142    type Direction = Forward;
143
144    fn transfer_function(
145        &mut self,
146        gen_kill_set: &mut GenKillSet<StatementId>,
147        basic_bock: BasicBlockId,
148        cfg: &ControlFlowGraph,
149    ) {
150        for stmt in cfg[basic_bock].statements.iter().copied() {
151            match self.mir[stmt] {
152                Statement::Assignment(_, var, _) => {
153                    gen_kill_set.kill_all(&self.graph.assignments[var]);
154                    gen_kill_set.gen(stmt);
155                }
156
157                // branches are currently not tracked
158                Statement::Contribute(_, _, _, _) => {}
159            }
160        }
161    }
162
163    fn max_idx(&self) -> Self::SetType {
164        self.graph.len_stmd_idx()
165    }
166}
167
168struct UseDefBuilder<'lt> {
169    graph: &'lt mut UseDefGraph,
170    use_stmt: StatementId,
171}
172
173impl<'lt> DependencyHandler for UseDefBuilder<'lt> {
174    fn handle_variable_reference(&mut self, var: VariableId) {
175        self.graph.stmt_use_def_chains[self.use_stmt].union_with(&self.graph.assignments[var])
176        // todo do intersection here for stateful lint (worse performance but should be okay)
177    }
178
179    fn handle_parameter_reference(&mut self, _: ParameterId) {}
180
181    fn handle_branch_reference(&mut self, _: DisciplineAccess, _: BranchId, _: u8) {}
182
183    fn handle_system_function_call(
184        &mut self,
185        _: SystemFunctionCall<RealExpressionId, StringExpressionId, PortId, ParameterId>,
186    ) {
187    }
188}
189
190struct UseDefTerminatorBuilder<'lt> {
191    graph: &'lt mut UseDefGraph,
192    use_terminator_block: BasicBlockId,
193}
194
195impl<'lt> DependencyHandler for UseDefTerminatorBuilder<'lt> {
196    fn handle_variable_reference(&mut self, var: VariableId) {
197        self.graph.terminator_use_def_chains[self.use_terminator_block]
198            .union_with(&self.graph.assignments[var]);
199    }
200
201    fn handle_parameter_reference(&mut self, _: ParameterId) {}
202
203    fn handle_branch_reference(&mut self, _: DisciplineAccess, _: BranchId, _: u8) {}
204
205    fn handle_system_function_call(
206        &mut self,
207        _: SystemFunctionCall<RealExpressionId, StringExpressionId, PortId, ParameterId>,
208    ) {
209    }
210}
211
212#[cfg(feature = "graph_debug")]
213mod print {
214    use super::*;
215    use rustc_ap_graphviz as dot;
216    use rustc_ap_graphviz::LabelText::{EscStr, LabelStr};
217    use rustc_ap_graphviz::{Edges, GraphWalk, Id, LabelText, Labeller, Nodes};
218    use rustc_hash::FxHashSet;
219    use std::borrow::Cow;
220    use std::io::Write;
221
222    impl ControlFlowGraph {
223        pub fn render_data_dependence_to<W: Write>(&self, write: &mut W, udg: &UseDefGraph) {
224            dot::render(&DataDependenceGraph(self, udg), write).expect("Rendering failed")
225        }
226    }
227
228    struct DataDependenceGraph<'lt>(&'lt ControlFlowGraph, &'lt UseDefGraph);
229
230    #[derive(Copy, Clone, Eq, PartialEq)]
231    enum FlowOrDependence {
232        Flow,
233        Dependence,
234    }
235
236    impl<'a> dot::Labeller<'a> for DataDependenceGraph<'a> {
237        type Node = BasicBlockId;
238        type Edge = (FlowOrDependence, BasicBlockId, BasicBlockId);
239
240        fn graph_id(&'a self) -> Id<'a> {
241            dot::Id::new("ControlFlowGraph").unwrap()
242        }
243
244        fn node_id(&'a self, n: &Self::Node) -> Id<'a> {
245            dot::Id::new(format!("BB_{}", n.index())).unwrap()
246        }
247
248        fn node_label(&'a self, &n: &Self::Node) -> LabelText<'a> {
249            match self.0.blocks[n].terminator {
250                Terminator::End => EscStr(Cow::Owned(format!(
251                    "BB_{}: {} Statements\n END",
252                    n.index(),
253                    self.0.blocks[n].statements.len(),
254                ))),
255                Terminator::Goto(_) => LabelStr(Cow::Owned(format!(
256                    "BB_{}: {} Statements",
257                    n.index(),
258                    self.0.blocks[n].statements.len(),
259                ))),
260                Terminator::Split {
261                    condition, merge, ..
262                } => LabelStr(Cow::Owned(format!(
263                    "BB_{}: {} Statements\nSplit at {:?}\nMerge at BB_{}",
264                    n.index(),
265                    self.0.blocks[n].statements.len(),
266                    condition,
267                    merge.index(),
268                ))),
269            }
270        }
271        fn edge_label(
272            &'a self,
273            &(edge_type, start, dst): &(FlowOrDependence, BasicBlockId, BasicBlockId),
274        ) -> LabelText<'a> {
275            match edge_type {
276                FlowOrDependence::Flow => match self.0[start].terminator {
277                    Terminator::Goto(_) => LabelStr(Cow::Borrowed("GOTO")),
278                    Terminator::End => LabelStr(Cow::Borrowed("ILLEGAL")),
279                    Terminator::Split {
280                        condition,
281                        true_block,
282                        false_block,
283                        merge,
284                    } => {
285                        let true_or_false = if true_block == dst {
286                            "TRUE"
287                        } else if false_block == dst {
288                            "FALSE"
289                        } else {
290                            "ILLEGAL"
291                        };
292                        LabelStr(Cow::Borrowed(true_or_false))
293                    }
294                },
295
296                FlowOrDependence::Dependence => LabelStr(Cow::Borrowed("Data dependence")),
297            }
298        }
299    }
300
301    impl<'a> dot::GraphWalk<'a> for DataDependenceGraph<'a> {
302        type Node = BasicBlockId;
303        type Edge = (FlowOrDependence, BasicBlockId, BasicBlockId);
304
305        fn nodes(&'a self) -> Nodes<'a, Self::Node> {
306            Cow::Owned(self.0.blocks.indices().collect())
307        }
308
309        fn edges(&'a self) -> Edges<'a, Self::Edge> {
310            let mut edges = Vec::new();
311            for (id, bb) in self.0.blocks.iter_enumerated() {
312                match bb.terminator {
313                    Terminator::Goto(dst) => edges.push((FlowOrDependence::Flow, id, dst)),
314                    Terminator::Split {
315                        condition,
316                        true_block,
317                        false_block,
318                        merge,
319                    } => {
320                        edges.push((FlowOrDependence::Flow, id, false_block));
321                        edges.push((FlowOrDependence::Flow, id, true_block));
322                    }
323                    Terminator::End => (),
324                }
325            }
326            let mut processed_data_dependencies = FxHashSet::with_capacity_and_hasher(
327                self.0.blocks.len() * self.0.blocks.len(),
328                Default::default(),
329            );
330
331            for (src, data_dependencies) in self.1.stmt_use_def_chains.iter_enumerated() {
332                let src_block = self.0.containing_block(src).unwrap();
333                for dst in data_dependencies.ones() {
334                    let dst_block = self.0.containing_block(dst).unwrap();
335                    if processed_data_dependencies.insert((src_block, dst_block)) {
336                        edges.push((FlowOrDependence::Dependence, src_block, dst_block));
337                    }
338                }
339            }
340
341            for (src, data_dependencies) in self.1.terminator_use_def_chains.iter_enumerated() {
342                for dst in data_dependencies.ones() {
343                    let dst_block = self.0.containing_block(dst).unwrap();
344                    if processed_data_dependencies.insert((src, dst_block)) {
345                        edges.push((FlowOrDependence::Dependence, src, dst_block));
346                    }
347                }
348            }
349
350            Cow::Owned(edges)
351        }
352
353        fn source(&'a self, edge: &Self::Edge) -> Self::Node {
354            edge.1
355        }
356
357        fn target(&'a self, edge: &Self::Edge) -> Self::Node {
358            edge.2
359        }
360    }
361}
open_vaf/analysis/data_flow/reaching_variables.rs

open_vaf/analysis/data_flow/
reaching_variables.rs
