open_vaf/analysis/
program_slicing.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::ProgramDependenceGraph;
10use crate::data_structures::{BitSet, WorkQueue};
11use crate::ir::hir::DisciplineAccess;
12use crate::ir::{
13    BranchId, IntegerExpressionId, NoiseSource, ParameterId, PortId, RealExpressionId, StatementId,
14    StringExpressionId, SystemFunctionCall, VariableId,
15};
16use crate::mir::{ExpressionId, Mir, StringExpression};
17use crate::mir::{IntegerExpression, RealExpression};
18use crate::ControlFlowGraph;
19use log::*;
20use std::collections::VecDeque;
21use std::iter::FromIterator;
22
23impl ControlFlowGraph {
24    pub fn backward_variable_slice(&mut self, var: VariableId, pdg: &ProgramDependenceGraph) {
25        let relevant_stmts = pdg.data_dependencies.assignments[var].clone();
26        self.backward_slice(relevant_stmts, BitSet::new_empty(StatementId::new(0)), pdg);
27    }
28
29    pub fn backward_variable_slice_assuming_input(
30        &mut self,
31        input: BitSet<StatementId>,
32        var: VariableId,
33        pdg: &ProgramDependenceGraph,
34    ) {
35        let relevant_stmts = pdg.data_dependencies.assignments[var].clone();
36        self.backward_slice(relevant_stmts, input, pdg);
37    }
38
39    pub fn backward_variable_slice_with_variables_as_input(
40        &mut self,
41        input: impl Iterator<Item = VariableId>,
42        var: VariableId,
43        pdg: &ProgramDependenceGraph,
44    ) {
45        let mut input_statements =
46            BitSet::new_empty(pdg.data_dependencies.stmt_use_def_chains.len_idx());
47        for var in input {
48            input_statements.union_with(&pdg.data_dependencies.assignments[var])
49        }
50        self.backward_variable_slice_assuming_input(input_statements, var, pdg)
51    }
52
53    pub fn backward_slice(
54        &mut self,
55        mut relevant_stmts: BitSet<StatementId>,
56        assumed_stmts: BitSet<StatementId>,
57        pdg: &ProgramDependenceGraph,
58    ) {
59        debug!(
60            "Computing backwardslice wit intput {} and output {}",
61            assumed_stmts,
62            relevant_stmts
63        );
64        // The assumed stmts are marked as visited so they wont be inserted into the work queue
65        let mut set = assumed_stmts;
66        // The relevant stmts are added to the work queue
67        set.grow(relevant_stmts.len_idx());
68        set.union(&relevant_stmts);
69        let mut stmt_work_queue = WorkQueue {
70            // Add all relevant stmts to the work queue
71            deque: VecDeque::from_iter(relevant_stmts.ones()),
72            set,
73        };
74
75        trace!(
76            "Backwardslice: Inital stmt work-list: {:?}",
77            stmt_work_queue
78        );
79
80        let mut bb_work_queue = WorkQueue::with_none(self.blocks.len_idx());
81
82
83        loop {
84            let mut done = true;
85
86            if let Some(stmt) = stmt_work_queue.take() {
87                relevant_stmts.insert(stmt);
88                for data_dependency in pdg.data_dependencies.stmt_use_def_chains[stmt].ones() {
89                    stmt_work_queue.insert(data_dependency);
90                }
91
92                for control_dependency in pdg.control_dependencies[self
93                    .containing_block(stmt)
94                    .expect("Mallformed cfg statement owners")]
95                .ones()
96                {
97                    bb_work_queue.insert(control_dependency);
98                }
99
100                trace!(
101                    "Backwardslice: Inital stmt work-list after iteration {:?}",
102                    stmt_work_queue
103                );
104                done = false;
105            }
106
107            if let Some(bb) = bb_work_queue.take() {
108                for data_dependency in pdg.data_dependencies.terminator_use_def_chains[bb].ones() {
109                    stmt_work_queue.insert(data_dependency);
110                }
111
112                for control_dependency in pdg.control_dependencies[bb].ones() {
113                    bb_work_queue.insert(control_dependency);
114                }
115
116                done = false;
117            }
118
119            if done {
120                break;
121            }
122        }
123
124        for bb in self.blocks.iter_mut() {
125            bb.statements.retain(|&stmt| relevant_stmts.contains(stmt))
126        }
127    }
128}
129
130impl Mir {
131    pub fn track_expression(
132        &self,
133        expr: ExpressionId,
134        dependency_handler: &mut impl DependencyHandler,
135    ) {
136        match expr {
137            ExpressionId::Real(expr) => self.track_real_expression(expr, dependency_handler),
138            ExpressionId::Integer(expr) => self.track_integer_expression(expr, dependency_handler),
139            ExpressionId::String(expr) => self.track_string_expression(expr, dependency_handler),
140        }
141    }
142
143    pub fn track_real_expression(
144        &self,
145        expr: RealExpressionId,
146        dependency_handler: &mut impl DependencyHandler,
147    ) {
148        match self[expr].contents {
149            RealExpression::Literal(_) => (),
150            RealExpression::VariableReference(var) => {
151                dependency_handler.handle_variable_reference(var);
152            }
153            RealExpression::ParameterReference(param) => {
154                dependency_handler.handle_parameter_reference(param)
155            }
156            RealExpression::Vt(temp) => {
157                dependency_handler.handle_system_function_call(SystemFunctionCall::Vt(temp))
158            }
159            RealExpression::SimParam(name, default) => dependency_handler
160                .handle_system_function_call(SystemFunctionCall::Simparam(name, default)),
161            RealExpression::Temperature => {
162                dependency_handler.handle_system_function_call(SystemFunctionCall::Temperature)
163            }
164
165            RealExpression::Noise(source, _) => match source {
166                NoiseSource::White(expr) => self.track_real_expression(expr, dependency_handler),
167                NoiseSource::Flicker(expr1, expr2) => {
168                    self.track_real_expression(expr1, dependency_handler);
169                    self.track_real_expression(expr2, dependency_handler);
170                }
171                NoiseSource::Table(_) | NoiseSource::TableLog(_) => todo!(),
172            },
173
174            RealExpression::BuiltInFunctionCall2p(_, arg1, arg2)
175            | RealExpression::BinaryOperator(arg1, _, arg2) => {
176                self.track_real_expression(arg1, dependency_handler);
177                self.track_real_expression(arg2, dependency_handler);
178            }
179
180            RealExpression::Condition(cond, _, val1, _, val2) => {
181                self.track_integer_expression(cond, dependency_handler);
182                self.track_real_expression(val1, dependency_handler);
183                self.track_real_expression(val2, dependency_handler);
184            }
185
186            RealExpression::BranchAccess(discipline, branch, order) => {
187                dependency_handler.handle_branch_reference(discipline, branch, order)
188            }
189
190            RealExpression::Negate(_, expr) | RealExpression::BuiltInFunctionCall1p(_, expr) => {
191                self.track_real_expression(expr, dependency_handler)
192            }
193            RealExpression::IntegerConversion(expr) => {
194                self.track_integer_expression(expr, dependency_handler)
195            }
196        }
197    }
198
199    pub fn track_integer_expression(
200        &self,
201        expr: IntegerExpressionId,
202        dependency_handler: &mut impl DependencyHandler,
203    ) {
204        match self[expr].contents {
205            IntegerExpression::Literal(_) => (),
206
207            IntegerExpression::VariableReference(var) => {
208                dependency_handler.handle_variable_reference(var);
209            }
210            IntegerExpression::ParameterReference(param) => {
211                dependency_handler.handle_parameter_reference(param)
212            }
213
214            IntegerExpression::NetReference(_) | IntegerExpression::PortReference(_) => {
215                todo!("digital")
216            }
217
218            IntegerExpression::FunctionCall(_, _) => todo!("Function calls"),
219
220            IntegerExpression::StringEq(arg1, arg2) | IntegerExpression::StringNEq(arg1, arg2) => {
221                self.track_string_expression(arg1, dependency_handler);
222                self.track_string_expression(arg2, dependency_handler);
223            }
224
225            IntegerExpression::RealComparison(arg1, _, arg2) => {
226                self.track_real_expression(arg1, dependency_handler);
227                self.track_real_expression(arg2, dependency_handler);
228            }
229
230            IntegerExpression::RealCast(expr) => {
231                self.track_real_expression(expr, dependency_handler);
232            }
233
234            IntegerExpression::UnaryOperator(_, expr) | IntegerExpression::Abs(expr) => {
235                self.track_integer_expression(expr, dependency_handler)
236            }
237
238            IntegerExpression::Max(arg1, arg2)
239            | IntegerExpression::Min(arg1, arg2)
240            | IntegerExpression::BinaryOperator(arg1, _, arg2)
241            | IntegerExpression::IntegerComparison(arg1, _, arg2) => {
242                self.track_integer_expression(arg1, dependency_handler);
243                self.track_integer_expression(arg2, dependency_handler);
244            }
245
246            IntegerExpression::Condition(cond, _, val1, _, val2) => {
247                self.track_integer_expression(cond, dependency_handler);
248                self.track_integer_expression(val1, dependency_handler);
249                self.track_integer_expression(val2, dependency_handler);
250            }
251            IntegerExpression::ParamGiven(param) => dependency_handler
252                .handle_system_function_call(SystemFunctionCall::ParameterGiven(param)),
253            IntegerExpression::PortConnected(port) => dependency_handler
254                .handle_system_function_call(SystemFunctionCall::PortConnected(port)),
255        }
256    }
257
258    pub fn track_string_expression(
259        &self,
260        expr: StringExpressionId,
261        dependency_handler: &mut impl DependencyHandler,
262    ) {
263        match self[expr].contents {
264            StringExpression::Literal(_) => (),
265            StringExpression::VariableReference(var) => {
266                dependency_handler.handle_variable_reference(var);
267            }
268            StringExpression::Condition(cond, _, val1, _, val2) => {
269                self.track_integer_expression(cond, dependency_handler);
270                self.track_string_expression(val1, dependency_handler);
271                self.track_string_expression(val2, dependency_handler);
272            }
273            StringExpression::ParameterReference(param) => {
274                dependency_handler.handle_parameter_reference(param)
275            }
276            StringExpression::SimParam(name) => dependency_handler
277                .handle_system_function_call(SystemFunctionCall::SimparamStr(name)),
278        }
279    }
280}
281
282pub trait DependencyHandler {
283    fn handle_variable_reference(&mut self, var: VariableId);
284    fn handle_parameter_reference(&mut self, param: ParameterId);
285    fn handle_branch_reference(&mut self, access: DisciplineAccess, branch: BranchId, order: u8);
286    fn handle_system_function_call(
287        &mut self,
288        call: SystemFunctionCall<RealExpressionId, StringExpressionId, PortId, ParameterId>,
289    );
290}
291
292impl DependencyHandler for () {
293    fn handle_variable_reference(&mut self, _: VariableId) {}
294
295    fn handle_parameter_reference(&mut self, _: ParameterId) {}
296
297    fn handle_branch_reference(&mut self, _: DisciplineAccess, _: BranchId, _: u8) {}
298
299    fn handle_system_function_call(
300        &mut self,
301        _: SystemFunctionCall<RealExpressionId, StringExpressionId, PortId, ParameterId>,
302    ) {
303    }
304}
open_vaf/analysis/program_slicing.rs

open_vaf/analysis/
program_slicing.rs
