open_vaf/ir/cfg/transversal.rs
1/*
2
3 * ******************************************************************************************
4 * Copyright (c) 2019 Pascal Kuthe. This file is part of the OpenVAF project.
5 * It is subject to the license terms in the LICENSE file found in the top-level directory
6 * of this distribution and at https://gitlab.com/DSPOM/OpenVAF/blob/master/LICENSE.
7 * No part of OpenVAF, including this file, may be copied, modified, propagated, or
8 * distributed except according to the terms contained in the LICENSE file.
9 * *****************************************************************************************
10
11 Adapted from https://github.com/rust-lang/rust src/librustc_middle/mir/traversal.rs under MIT-License
12
13 Permission is hereby granted, free of charge, to any person obtaining a copy
14 of this software and associated documentation files (the "Software"), to deal
15 in the Software without restriction, including without limitation the rights
16 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 copies of the Software, and to permit persons to whom the Software is
18 furnished to do so, subject to the following conditions:
19
20 The above copyright notice and this permission notice shall be included in all
21 copies or substantial portions of the Software.
22
23 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
24 ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
25 TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
26 PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
27 SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
28 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
30 IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
31 DEALINGS IN THE SOFTWARE.
32*/
33
34use crate::data_structures::BitSet;
35use crate::ir::cfg::{BasicBlock, BasicBlockId, ControlFlowGraph, Successors};
36/// Postorder traversal of a graph.
37///
38/// Postorder traversal is when each node is visited after all of its
39/// successors, except when the successor is only reachable by a back-edge
40///
41///
42/// ```text
43///
44/// A
45/// / \
46/// / \
47/// B C
48/// \ /
49/// \ /
50/// D
51/// ```
52///
53/// A Postorder traversal of this graph is `D B C A` or `D C B A`
54///
55pub struct Postorder {
56 visited: BitSet<BasicBlockId>,
57 visit_stack: Vec<(BasicBlockId, Successors)>,
58 root_is_start_block: bool,
59}
60
61impl<'lt> Postorder {
62 pub fn new(cfg: &ControlFlowGraph, root: BasicBlockId) -> Postorder {
63 let mut po = Postorder {
64 visited: BitSet::new_empty(cfg.blocks.len_idx()),
65 visit_stack: Vec::new(),
66 root_is_start_block: root == cfg.start(),
67 };
68
69 po.visited.insert(root);
70 po.visit_stack.push((root, cfg.successors(root)));
71 po.traverse_successor(cfg);
72
73 po
74 }
75
76 fn traverse_successor(&mut self, cfg: &ControlFlowGraph) {
77 // This is quite a complex loop due to 1. the borrow checker not liking it much
78 // and 2. what exactly is going on is not clear
79 //
80 // It does the actual traversal of the graph, while the `next` method on the iterator
81 // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
82 // iterators over the successors of those nodes. Each iteration attempts to get the next
83 // node from the top of the stack, then pushes that node and an iterator over the
84 // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
85 // we reach a child that has no children that we haven't already visited.
86 //
87 // For a graph that looks like this:
88 //
89 // A
90 // / \
91 // / \
92 // B C
93 // | |
94 // | |
95 // D |
96 // \ /
97 // \ /
98 // E
99 //
100 // The state of the stack starts out with just the root node (`A` in this case);
101 // [(A, [B, C])]
102 //
103 // When the first call to `traverse_successor` happens, the following happens:
104 //
105 // [(B, [D]), // `B` taken from the successors of `A`, pushed to the
106 // // top of the stack along with the successors of `B`
107 // (A, [C])]
108 //
109 // [(D, [E]), // `D` taken from successors of `B`, pushed to stack
110 // (B, []),
111 // (A, [C])]
112 //
113 // [(E, []), // `E` taken from successors of `D`, pushed to stack
114 // (D, []),
115 // (B, []),
116 // (A, [C])]
117 //
118 // Now that the top of the stack has no successors we can traverse, each item will
119 // be popped off during iteration until we get back to `A`. This yields [E, D, B].
120 //
121 // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
122 // since we've already visited `E`, that child isn't added to the stack. The last
123 // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
124 while let Some(bb) = self
125 .visit_stack
126 .last_mut()
127 .and_then(|(_, iter)| iter.next())
128 {
129 if !self.visited.put(bb) {
130 self.visit_stack.push((bb, cfg[bb].terminator.successors()));
131 }
132 }
133 }
134}
135
136pub struct PostorderIter<'lt> {
137 pub base: Postorder,
138 pub cfg: &'lt ControlFlowGraph,
139}
140
141impl<'lt> PostorderIter<'lt> {
142 pub fn new(cfg: &'lt ControlFlowGraph, root: BasicBlockId) -> Self {
143 Self {
144 base: Postorder::new(cfg, root),
145 cfg,
146 }
147 }
148}
149
150impl<'lt> Iterator for PostorderIter<'lt> {
151 type Item = (BasicBlockId, &'lt BasicBlock);
152
153 fn next(&mut self) -> Option<(BasicBlockId, &'lt BasicBlock)> {
154 let next = self.base.visit_stack.pop();
155 if next.is_some() {
156 self.base.traverse_successor(self.cfg);
157 }
158
159 next.map(|(bb, _)| (bb, &self.cfg[bb]))
160 }
161
162 fn size_hint(&self) -> (usize, Option<usize>) {
163 // All the blocks, minus the number of blocks we've visited.
164 let upper = self.cfg.blocks.len() - self.base.visited.ones().count();
165
166 let lower = if self.base.root_is_start_block {
167 // We will visit all remaining blocks exactly once.
168 upper
169 } else {
170 self.base.visit_stack.len()
171 };
172
173 (lower, Some(upper))
174 }
175}
176
177pub struct PostorderIterMut<'lt> {
178 base: Postorder,
179 cfg: &'lt mut ControlFlowGraph,
180}
181
182impl<'lt> PostorderIterMut<'lt> {
183 pub fn new(cfg: &'lt mut ControlFlowGraph, root: BasicBlockId) -> Self {
184 Self {
185 base: Postorder::new(cfg, root),
186 cfg,
187 }
188 }
189}
190
191impl<'lt> Iterator for PostorderIterMut<'lt> {
192 type Item = (BasicBlockId, &'lt mut BasicBlock);
193
194 fn next(&mut self) -> Option<(BasicBlockId, &'lt mut BasicBlock)> {
195 let next = self.base.visit_stack.pop();
196 if next.is_some() {
197 self.base.traverse_successor(self.cfg);
198 }
199
200 /*
201 This transmute is here to transmut `&'_ mut BasicBlock` to `&'lt mut BasicBlock`
202 This is save since the iterator already has an exclusive borrow of the ControlFlow Graph/Basic Blocks for 'lt
203 and only yields elements exactly once so not two mutable refences to the same block can be handed out.
204 Furthermore the mutable cfg reference is private so it can not be used from elsewhere to access the cfg.
205 Internally this iterator does read from the cfg. However it only ever reads from blocks that have not been visited yet.
206 As such this is also save since after hadning out a &'lt mut to a block it is never read internally either
207 */
208
209 next.map(|(bb, _)| (bb, unsafe { std::mem::transmute(&mut self.cfg[bb]) }))
210 }
211
212 fn size_hint(&self) -> (usize, Option<usize>) {
213 // All the blocks, minus the number of blocks we've visited.
214 let upper = self.cfg.blocks.len() - self.base.visited.ones().count();
215
216 let lower = if self.base.root_is_start_block {
217 // We will visit all remaining blocks exactly once.
218 upper
219 } else {
220 self.base.visit_stack.len()
221 };
222
223 (lower, Some(upper))
224 }
225}
226
227/// Reverse postorder traversal of a graph
228///
229/// Reverse postorder is the reverse order of a postorder traversal.
230/// This is different to a preorder traversal and represents a natural
231/// linearization of control-flow.
232///
233/// ```text
234///
235/// A
236/// / \
237/// / \
238/// B C
239/// \ /
240/// \ /
241/// D
242/// ```
243///
244/// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
245/// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
246/// a topological sort.
247///
248/// Construction of a `ReversePostorder` traversal requires doing a full
249/// postorder traversal of the graph, therefore this traversal should be
250/// constructed as few times as possible. Use the `reset` method to be able
251/// to re-use the traversal
252#[derive(Clone, Debug)]
253pub struct ReversePostorder {
254 blocks: Vec<BasicBlockId>,
255 idx: usize,
256}
257
258impl ReversePostorder {
259 pub fn new(cfg: &ControlFlowGraph, root: BasicBlockId) -> Self {
260 let blocks: Vec<_> = PostorderIter::new(cfg, root).map(|(bb, _)| bb).collect();
261
262 let len = blocks.len();
263
264 ReversePostorder { blocks, idx: len }
265 }
266
267 pub fn reset(&mut self) {
268 self.idx = self.blocks.len();
269 }
270}
271
272impl Iterator for ReversePostorder {
273 type Item = BasicBlockId;
274
275 fn next(&mut self) -> Option<BasicBlockId> {
276 if self.idx == 0 {
277 return None;
278 }
279 self.idx -= 1;
280
281 self.blocks.get(self.idx).copied()
282 }
283
284 fn size_hint(&self) -> (usize, Option<usize>) {
285 (self.idx, Some(self.idx))
286 }
287}
288
289impl ExactSizeIterator for ReversePostorder {}
290
291pub struct ReversePostorderIter<'lt> {
292 cfg: &'lt ControlFlowGraph,
293 base: ReversePostorder,
294}
295
296impl<'lt> ReversePostorderIter<'lt> {
297 pub fn new(cfg: &'lt ControlFlowGraph, root: BasicBlockId) -> Self {
298 Self {
299 base: ReversePostorder::new(cfg, root),
300 cfg,
301 }
302 }
303}
304
305impl<'lt> Iterator for ReversePostorderIter<'lt> {
306 type Item = (BasicBlockId, &'lt BasicBlock);
307
308 fn next(&mut self) -> Option<(BasicBlockId, &'lt BasicBlock)> {
309 self.base.next().map(|bb| (bb, &self.cfg[bb]))
310 }
311
312 fn size_hint(&self) -> (usize, Option<usize>) {
313 self.base.size_hint()
314 }
315}
316
317pub struct ReversePostorderIterMut<'lt> {
318 cfg: &'lt mut ControlFlowGraph,
319 base: ReversePostorder,
320}
321
322impl<'lt> ReversePostorderIterMut<'lt> {
323 pub fn new(cfg: &'lt mut ControlFlowGraph, root: BasicBlockId) -> Self {
324 Self {
325 base: ReversePostorder::new(cfg, root),
326 cfg,
327 }
328 }
329}
330
331impl<'lt> Iterator for ReversePostorderIterMut<'lt> {
332 type Item = (BasicBlockId, &'lt mut BasicBlock);
333
334 fn next(&mut self) -> Option<(BasicBlockId, &'lt mut BasicBlock)> {
335 /*
336 This transmute is here to transmut &'_ mut BasicBlock to &'lt mut BasicBlock
337 This is save since the iterator already has an exclusive borrow of the ControlFlow Graph/Basic Blocks for 'lt
338 and only yields elements exactly once so not two mutable refences to the same block can be handed out.
339 Furthermore the mutable cfg reference is private so it can not be used from elsewhere to access the cfg.
340 Internally this iterator never accesses the cfg (this is just a conviniance struct) so this is fine here
341 */
342 self.base
343 .next()
344 .map(|bb| (bb, unsafe { std::mem::transmute(&mut self.cfg[bb]) }))
345 }
346
347 fn size_hint(&self) -> (usize, Option<usize>) {
348 self.base.size_hint()
349 }
350}