open_vaf/ir/cfg/
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
9use crate::cfg::transversal::ReversePostorderIterMut;
10use crate::data_structures::BitSet;
11use crate::ir::cfg::predecessors::PredecessorCache;
12use crate::ir::cfg::statement_owner::StatementOwnerCache;
13use crate::ir::cfg::transversal::{
14    Postorder, PostorderIter, PostorderIterMut, ReversePostorder, ReversePostorderIter,
15};
16use crate::ir::mir::Mir;
17use crate::ir::{IntegerExpressionId, StatementId};
18use bitflags::_core::mem::MaybeUninit;
19use core::mem::swap;
20use index_vec::IndexVec;
21use log::trace;
22use rustc_hash::FxHashMap;
23use std::ops::Range;
24
25mod predecessors;
26#[cfg(feature = "graph_debug")]
27mod print;
28mod statement_owner;
29pub mod transversal;
30
31// Macros that call functions that produce a cfg with more or less blocks (and therefore a new tag)
32
33id_type!(BasicBlockId(u16));
34impl_id_type!(BasicBlockId in ControlFlowGraph::blocks -> BasicBlock);
35
36pub struct Successors {
37    data: [MaybeUninit<BasicBlockId>; 2],
38    len: u8,
39}
40
41impl Successors {
42    pub const fn new_empty() -> Self {
43        Self {
44            data: [MaybeUninit::uninit(), MaybeUninit::uninit()],
45            len: 0,
46        }
47    }
48
49    pub const fn new_single(block: BasicBlockId) -> Self {
50        Self {
51            data: [MaybeUninit::new(block), MaybeUninit::uninit()],
52            len: 1,
53        }
54    }
55
56    pub const fn new_double(block1: BasicBlockId, block2: BasicBlockId) -> Self {
57        Self {
58            data: [MaybeUninit::new(block1), MaybeUninit::new(block2)],
59            len: 2,
60        }
61    }
62}
63
64impl Iterator for Successors {
65    type Item = BasicBlockId;
66
67    fn next(&mut self) -> Option<Self::Item> {
68        if self.len > 0 {
69            self.len -= 1;
70            Some(unsafe { self.data[self.len as usize].assume_init() })
71        } else {
72            None
73        }
74    }
75
76    fn size_hint(&self) -> (usize, Option<usize>) {
77        (self.len as usize, Some(self.len as usize))
78    }
79}
80
81impl ExactSizeIterator for Successors {
82    fn len(&self) -> usize {
83        self.len as usize
84    }
85}
86
87#[derive(Clone, Debug)]
88pub struct ControlFlowGraph {
89    pub blocks: IndexVec<BasicBlockId, BasicBlock>,
90    pub(crate) predecessor_cache: PredecessorCache,
91    pub(crate) statement_owner_cache: StatementOwnerCache,
92}
93
94impl ControlFlowGraph {
95    #[inline]
96    pub fn new(blocks: IndexVec<BasicBlockId, BasicBlock>, mir: &Mir) -> Self {
97        Self {
98            blocks,
99            predecessor_cache: PredecessorCache::new(),
100            statement_owner_cache: StatementOwnerCache::new(mir.statements.len()),
101        }
102    }
103
104    #[inline(always)]
105    pub fn start(&self) -> BasicBlockId {
106        // The last element
107        self.blocks.len_idx() - 1
108    }
109
110    #[inline(always)]
111    pub const fn end(&self) -> BasicBlockId {
112        BasicBlockId::from_raw_unchecked(0)
113    }
114
115    // transversals
116
117    pub fn postorder(&self) -> Postorder {
118        Postorder::new(self, self.start())
119    }
120
121    pub fn postorder_iter(&self) -> PostorderIter {
122        PostorderIter::new(self, self.start())
123    }
124
125    pub fn postorder_itermut(&mut self) -> PostorderIterMut {
126        PostorderIterMut::new(self, self.start())
127    }
128
129    pub fn reverse_postorder(&self) -> ReversePostorder {
130        ReversePostorder::new(self, self.start())
131    }
132
133    pub fn reverse_postorder_iter(&self) -> ReversePostorderIter<'_> {
134        ReversePostorderIter::new(self, self.start())
135    }
136
137    pub fn reverse_postorder_itermut(&mut self) -> ReversePostorderIterMut {
138        ReversePostorderIterMut::new(self, self.start())
139    }
140
141    // Relations
142
143    pub fn predecessors(&self, bb: BasicBlockId) -> &[BasicBlockId] {
144        &self.predecessor_cache.compute(&self.blocks)[bb]
145    }
146
147    pub fn containing_block(&self, stmt: StatementId) -> Option<BasicBlockId> {
148        self.statement_owner_cache
149            .compute(self)
150            .get(stmt)
151            .copied()
152            .flatten()
153    }
154
155    pub fn successors(&self, bb: BasicBlockId) -> Successors {
156        self[bb].successors()
157    }
158
159    // Transformations
160
161    pub fn simplify(&mut self) {
162        let mut new_replacements: FxHashMap<BasicBlockId, BasicBlockId> = FxHashMap::default();
163        let mut replacements = new_replacements.clone();
164        let mut dead_blocks = BitSet::new_empty(self.blocks.len_idx());
165        dead_blocks.extend(self.postorder_iter().map(|(id, _)| id));
166        dead_blocks.toggle_range(..);
167        // TODO rewrite as worklist algorithm
168        loop {
169            let mut replacement_targets = BitSet::new_empty(self.blocks.len_idx());
170            let mut changed = false;
171
172            for (id, block) in self.blocks.iter_mut_enumerated() {
173                if dead_blocks.contains(id) {
174                    continue;
175                }
176
177                match block.terminator {
178                    Terminator::End => (),
179                    Terminator::Goto(ref mut next) => {
180                        if let Some(&new_next) = replacements.get(next) {
181                            *next = new_next
182                        }
183
184                        let next = *next;
185                        if block.statements.is_empty()
186                            && !replacement_targets.contains(id)
187                            && !new_replacements.contains_key(&next)
188                        {
189                            new_replacements.insert(id, next);
190                            dead_blocks.insert(id);
191                            replacement_targets.insert(next);
192                        }
193                    }
194
195                    Terminator::Split {
196                        condition,
197                        mut true_block,
198                        mut false_block,
199                        mut merge,
200                    } => {
201                        if let Some(&new_true_block) = replacements.get(&true_block) {
202                            true_block = new_true_block
203                        }
204
205                        if let Some(&new_false_block) = replacements.get(&false_block) {
206                            false_block = new_false_block
207                        }
208
209                        if let Some(&new_merge) = replacements.get(&merge) {
210                            merge = new_merge
211                        }
212
213                        block.terminator = if true_block == false_block {
214                            //empty condition
215                            changed = true;
216                            Terminator::Goto(merge)
217                        } else if true_block == id {
218                            //empty loop
219                            changed = true;
220                            Terminator::Goto(false_block)
221                        } else {
222                            Terminator::Split {
223                                condition,
224                                true_block,
225                                false_block,
226                                merge,
227                            }
228                        };
229                    }
230                };
231            }
232
233            if new_replacements.is_empty() && !changed {
234                break;
235            }
236
237            trace!(
238                "running because changed: {} or replacements: {:#?}",
239                changed,
240                new_replacements
241            );
242
243            swap(&mut new_replacements, &mut replacements);
244            new_replacements.clear();
245        }
246        self.remove_dead_code(&dead_blocks);
247    }
248
249    pub fn remove_dead_code(&mut self, dead_blocks: &BitSet<BasicBlockId>) {
250        let mut replacements = FxHashMap::default();
251
252        // adopted from std::vec::Vec::retain to fit the needs here
253        let len = self.blocks.len();
254        let mut del = 0;
255
256        for id in self.blocks.indices() {
257            if dead_blocks.contains(id) {
258                del += 1;
259            } else if del > 0 {
260                self.blocks.swap(id - del, id);
261                replacements.insert(id, id - del);
262            }
263        }
264
265        if del > 0 {
266            self.blocks.truncate(len - del);
267        }
268
269        for block in self.blocks.indices() {
270            match self.blocks[block].terminator {
271                Terminator::End => (),
272
273                Terminator::Goto(ref mut next) => {
274                    if let Some(&new_next) = replacements.get(next) {
275                        *next = new_next
276                    }
277                }
278                Terminator::Split {
279                    ref mut true_block,
280                    ref mut false_block,
281                    ref mut merge,
282                    ..
283                } => {
284                    if let Some(&new_true_block) = replacements.get(true_block) {
285                        *true_block = new_true_block
286                    }
287
288                    if let Some(&new_false_block) = replacements.get(false_block) {
289                        *false_block = new_false_block
290                    }
291
292                    if let Some(&new_merge) = replacements.get(merge) {
293                        *merge = new_merge
294                    }
295                }
296            }
297        }
298        self.statement_owner_cache.invalidate();
299        self.predecessor_cache.invalidate();
300    }
301}
302
303#[derive(Clone, Debug)]
304pub struct BasicBlock {
305    pub statements: Vec<StatementId>,
306    pub terminator: Terminator,
307}
308
309#[derive(Copy, Clone, Debug, PartialEq, Eq)]
310pub enum Terminator {
311    Goto(BasicBlockId),
312    Split {
313        condition: IntegerExpressionId,
314        true_block: BasicBlockId,
315        false_block: BasicBlockId,
316        merge: BasicBlockId,
317    },
318    End,
319}
320
321impl Terminator {
322    #[must_use]
323    pub fn successors(&self) -> Successors {
324        match self {
325            Self::End => Successors::new_empty(),
326            Self::Goto(dst) => Successors::new_single(*dst),
327            Self::Split {
328                true_block,
329                false_block,
330                ..
331            } => Successors::new_double(*true_block, *false_block),
332        }
333    }
334}
335
336impl BasicBlock {
337    pub fn successors(&self) -> Successors {
338        self.terminator.successors()
339    }
340}
open_vaf/ir/cfg/mod.rs

open_vaf/ir/cfg/
mod.rs
