open_vaf/analysis/data_flow/framework/
mod.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
9pub use engine::Engine;
10pub use graph::Graph as DataFlowGraph;
11
12mod engine;
13mod graph;
14
15use crate::data_structures::{BitSet, WorkQueue};
16use crate::ir::cfg::{BasicBlockId, ControlFlowGraph};
17use index_vec::{Idx, IndexVec};
18
19pub trait GenKillAnalysis<'lt>: Sized {
20    type SetType: Idx + From<usize>;
21    type Direction: Direction<'lt>;
22
23    fn transfer_function(
24        &mut self,
25        gen_kill_set: &mut GenKillSet<Self::SetType>,
26        basic_bock: BasicBlockId,
27        cfg: &ControlFlowGraph,
28    );
29
30    fn max_idx(&self) -> Self::SetType;
31}
32
33pub trait Analysis<'lt>: Sized {
34    type SetType: Idx + From<usize>;
35    type Direction: Direction<'lt>;
36
37    fn transfer_function(
38        &mut self,
39        in_set: &BitSet<Self::SetType>,
40        out_set: &mut BitSet<Self::SetType>,
41        basic_bock: BasicBlockId,
42        cfg: &ControlFlowGraph,
43    );
44
45    fn join(&mut self, inout_set: &mut BitSet<Self::SetType>, in_set: &BitSet<Self::SetType>) {
46        inout_set.union_with(in_set);
47    }
48
49    fn max_idx(&self) -> Self::SetType;
50}
51
52pub trait Direction<'lt> {
53    fn inital_work_queue(cfg: &ControlFlowGraph) -> WorkQueue<BasicBlockId>;
54    fn propagate_result(bb: BasicBlockId, cfg: &ControlFlowGraph, apply: impl FnMut(BasicBlockId));
55}
56
57pub struct Forward;
58
59impl<'lt> Direction<'lt> for Forward {
60    fn inital_work_queue(cfg: &ControlFlowGraph) -> WorkQueue<BasicBlockId> {
61        let mut res = WorkQueue::with_none(cfg.blocks.len_idx());
62        for id in cfg.reverse_postorder() {
63            res.insert(id);
64        }
65        res
66    }
67
68    fn propagate_result(
69        bb: BasicBlockId,
70        cfg: &ControlFlowGraph,
71        mut apply: impl FnMut(BasicBlockId),
72    ) {
73        for bb in cfg.successors(bb) {
74            apply(bb)
75        }
76    }
77}
78
79pub struct Backward;
80
81impl<'lt> Direction<'lt> for Backward {
82    fn inital_work_queue(cfg: &ControlFlowGraph) -> WorkQueue<BasicBlockId> {
83        let mut res = WorkQueue::with_none(cfg.blocks.len_idx());
84        for (id, _) in cfg.postorder_iter() {
85            res.insert(id);
86        }
87        res
88    }
89
90    fn propagate_result(
91        bb: BasicBlockId,
92        cfg: &ControlFlowGraph,
93        mut apply: impl FnMut(BasicBlockId),
94    ) {
95        for &bb in cfg.predecessors(bb) {
96            apply(bb)
97        }
98    }
99}
100
101pub struct GenKillEngine<'lt, A: GenKillAnalysis<'lt>> {
102    analysis: &'lt mut A,
103    pub transfer_functions: IndexVec<BasicBlockId, GenKillSet<A::SetType>>,
104}
105
106impl<'lt, A: GenKillAnalysis<'lt>> GenKillEngine<'lt, A> {
107    pub fn new(cfg: &ControlFlowGraph, analysis: &'lt mut A) -> Self {
108        let gen_kill_set = GenKillSet::new(analysis.max_idx());
109        let transfer_functions = cfg
110            .blocks
111            .indices()
112            .map(|bb| {
113                let mut transfer_function = gen_kill_set.clone();
114                analysis.transfer_function(&mut transfer_function, bb, cfg);
115                transfer_function
116            })
117            .collect();
118
119        Self {
120            analysis,
121            transfer_functions,
122        }
123    }
124}
125
126impl<'lt, A: GenKillAnalysis<'lt>> Analysis<'lt> for GenKillEngine<'lt, A> {
127    type SetType = A::SetType;
128    type Direction = A::Direction;
129
130    fn transfer_function(
131        &mut self,
132        in_set: &BitSet<Self::SetType>,
133        out_set: &mut BitSet<Self::SetType>,
134        basic_bock: BasicBlockId,
135        _: &ControlFlowGraph,
136    ) {
137        out_set.clear();
138        out_set.union_with(in_set);
139        out_set.difference_with(&self.transfer_functions[basic_bock].kill);
140        out_set.union_with(&self.transfer_functions[basic_bock].gen);
141    }
142    fn max_idx(&self) -> Self::SetType {
143        self.analysis.max_idx()
144    }
145}
146
147#[derive(Clone)]
148pub struct GenKillSet<I: Idx + From<usize>> {
149    pub gen: BitSet<I>,
150    pub kill: BitSet<I>,
151}
152
153impl<I: Idx + From<usize>> GenKillSet<I> {
154    #[inline]
155    pub fn new(max_idx: I) -> Self {
156        let gen = BitSet::new_empty(max_idx);
157        Self {
158            kill: gen.clone(),
159            gen,
160        }
161    }
162
163    #[inline]
164    pub fn gen(&mut self, x: I) {
165        self.gen.insert(x);
166        self.kill.set(x, false);
167    }
168
169    #[inline]
170    pub fn kill(&mut self, x: I) {
171        self.kill.insert(x);
172        self.gen.set(x, false);
173    }
174
175    #[inline]
176    pub fn kill_all(&mut self, kill: &BitSet<I>) {
177        self.kill.union_with(kill);
178        self.gen.difference_with(kill);
179    }
180
181    #[inline]
182    pub fn gen_all(&mut self, gen: &BitSet<I>) {
183        self.gen.union_with(gen);
184        self.kill.difference_with(gen);
185    }
186}
open_vaf/analysis/data_flow/framework/mod.rs

open_vaf/analysis/data_flow/framework/
mod.rs
