1 // Copyright © 2023 Collabora, Ltd.
2 // SPDX-License-Identifier: MIT
3
4 use crate::bitset::BitSet;
5 use std::collections::HashMap;
6 use std::hash::Hash;
7 use std::ops::{Deref, DerefMut, Index, IndexMut};
8 use std::slice;
9
10 pub struct CFGNode<N> {
11 node: N,
12 dom: usize,
13 dom_pre_idx: usize,
14 dom_post_idx: usize,
15 lph: usize,
16 pred: Vec<usize>,
17 succ: Vec<usize>,
18 }
19
20 impl<N> Deref for CFGNode<N> {
21 type Target = N;
22
deref(&self) -> &N23 fn deref(&self) -> &N {
24 &self.node
25 }
26 }
27
28 impl<N> DerefMut for CFGNode<N> {
deref_mut(&mut self) -> &mut N29 fn deref_mut(&mut self) -> &mut N {
30 &mut self.node
31 }
32 }
33
graph_post_dfs<N>( nodes: &Vec<CFGNode<N>>, id: usize, seen: &mut BitSet, post_idx: &mut Vec<usize>, count: &mut usize, )34 fn graph_post_dfs<N>(
35 nodes: &Vec<CFGNode<N>>,
36 id: usize,
37 seen: &mut BitSet,
38 post_idx: &mut Vec<usize>,
39 count: &mut usize,
40 ) {
41 if seen.get(id) {
42 return;
43 }
44 seen.insert(id);
45
46 // Reverse the order of the successors so that any successors which are
47 // forward edges get descending indices. This ensures that, in the reverse
48 // post order, successors (and their dominated children) come in-order.
49 // In particular, as long as fall-through edges are only ever used for
50 // forward edges and the fall-through edge comes first, we guarantee that
51 // the fallthrough block comes immediately after its predecessor.
52 for s in nodes[id].succ.iter().rev() {
53 graph_post_dfs(nodes, *s, seen, post_idx, count);
54 }
55
56 post_idx[id] = *count;
57 *count += 1;
58 }
59
rev_post_order_sort<N>(nodes: &mut Vec<CFGNode<N>>)60 fn rev_post_order_sort<N>(nodes: &mut Vec<CFGNode<N>>) {
61 let mut seen = BitSet::new();
62 let mut post_idx = Vec::new();
63 post_idx.resize(nodes.len(), usize::MAX);
64 let mut count = 0;
65
66 graph_post_dfs(nodes, 0, &mut seen, &mut post_idx, &mut count);
67
68 assert!(count <= nodes.len());
69
70 let remap_idx = |i: usize| {
71 let pid = post_idx[i];
72 if pid == usize::MAX {
73 None
74 } else {
75 assert!(pid < count);
76 Some((count - 1) - pid)
77 }
78 };
79 assert!(remap_idx(0) == Some(0));
80
81 // Re-map edges to use post-index numbering
82 for n in nodes.iter_mut() {
83 let remap_filter_idx = |i: &mut usize| {
84 if let Some(r) = remap_idx(*i) {
85 *i = r;
86 true
87 } else {
88 false
89 }
90 };
91 n.pred.retain_mut(remap_filter_idx);
92 n.succ.retain_mut(remap_filter_idx);
93 }
94
95 // We know a priori that each non-MAX post_idx is unique so we can sort the
96 // nodes by inserting them into a new array by index.
97 let mut sorted: Vec<CFGNode<N>> = Vec::with_capacity(count);
98 for (i, n) in nodes.drain(..).enumerate() {
99 if let Some(r) = remap_idx(i) {
100 unsafe { sorted.as_mut_ptr().add(r).write(n) };
101 }
102 }
103 unsafe { sorted.set_len(count) };
104
105 std::mem::swap(nodes, &mut sorted);
106 }
107
find_common_dom<N>( nodes: &Vec<CFGNode<N>>, mut a: usize, mut b: usize, ) -> usize108 fn find_common_dom<N>(
109 nodes: &Vec<CFGNode<N>>,
110 mut a: usize,
111 mut b: usize,
112 ) -> usize {
113 while a != b {
114 while a > b {
115 a = nodes[a].dom;
116 }
117 while b > a {
118 b = nodes[b].dom;
119 }
120 }
121 a
122 }
123
dom_idx_dfs<N>( nodes: &mut Vec<CFGNode<N>>, dom_children: &Vec<Vec<usize>>, id: usize, count: &mut usize, )124 fn dom_idx_dfs<N>(
125 nodes: &mut Vec<CFGNode<N>>,
126 dom_children: &Vec<Vec<usize>>,
127 id: usize,
128 count: &mut usize,
129 ) {
130 nodes[id].dom_pre_idx = *count;
131 *count += 1;
132
133 for c in dom_children[id].iter() {
134 dom_idx_dfs(nodes, dom_children, *c, count);
135 }
136
137 nodes[id].dom_post_idx = *count;
138 *count += 1;
139 }
140
calc_dominance<N>(nodes: &mut Vec<CFGNode<N>>)141 fn calc_dominance<N>(nodes: &mut Vec<CFGNode<N>>) {
142 nodes[0].dom = 0;
143 loop {
144 let mut changed = false;
145 for i in 1..nodes.len() {
146 let mut dom = nodes[i].pred[0];
147 for p in &nodes[i].pred[1..] {
148 if nodes[*p].dom != usize::MAX {
149 dom = find_common_dom(nodes, dom, *p);
150 }
151 }
152 assert!(dom != usize::MAX);
153 if nodes[i].dom != dom {
154 nodes[i].dom = dom;
155 changed = true;
156 }
157 }
158
159 if !changed {
160 break;
161 }
162 }
163
164 let mut dom_children = Vec::new();
165 dom_children.resize(nodes.len(), Vec::new());
166
167 for i in 1..nodes.len() {
168 let p = nodes[i].dom;
169 if p != i {
170 dom_children[p].push(i);
171 }
172 }
173
174 let mut count = 0_usize;
175 dom_idx_dfs(nodes, &dom_children, 0, &mut count);
176 debug_assert!(count == nodes.len() * 2);
177 }
178
loop_detect_dfs<N>( nodes: &Vec<CFGNode<N>>, id: usize, pre: &mut BitSet, post: &mut BitSet, loops: &mut BitSet, )179 fn loop_detect_dfs<N>(
180 nodes: &Vec<CFGNode<N>>,
181 id: usize,
182 pre: &mut BitSet,
183 post: &mut BitSet,
184 loops: &mut BitSet,
185 ) {
186 if pre.get(id) {
187 if !post.get(id) {
188 loops.insert(id);
189 }
190 return;
191 }
192
193 pre.insert(id);
194
195 for s in nodes[id].succ.iter() {
196 loop_detect_dfs(nodes, *s, pre, post, loops);
197 }
198
199 post.insert(id);
200 }
201
detect_loops<N>(nodes: &mut Vec<CFGNode<N>>) -> bool202 fn detect_loops<N>(nodes: &mut Vec<CFGNode<N>>) -> bool {
203 let mut dfs_pre = BitSet::new();
204 let mut dfs_post = BitSet::new();
205 let mut loops = BitSet::new();
206 loop_detect_dfs(nodes, 0, &mut dfs_pre, &mut dfs_post, &mut loops);
207
208 let mut has_loop = false;
209 nodes[0].lph = usize::MAX;
210 for i in 1..nodes.len() {
211 if loops.get(i) {
212 // This is a loop header
213 nodes[i].lph = i;
214 has_loop = true;
215 } else {
216 // Otherwise, we have the same loop header as our dominator
217 let dom = nodes[i].dom;
218 let dom_lph = nodes[dom].lph;
219 nodes[i].lph = dom_lph;
220 }
221 }
222
223 has_loop
224 }
225
226 pub struct CFG<N> {
227 has_loop: bool,
228 nodes: Vec<CFGNode<N>>,
229 }
230
231 impl<N> CFG<N> {
from_blocks_edges( nodes: impl IntoIterator<Item = N>, edges: impl IntoIterator<Item = (usize, usize)>, ) -> Self232 pub fn from_blocks_edges(
233 nodes: impl IntoIterator<Item = N>,
234 edges: impl IntoIterator<Item = (usize, usize)>,
235 ) -> Self {
236 let mut nodes = Vec::from_iter(nodes.into_iter().map(|n| CFGNode {
237 node: n,
238 dom: usize::MAX,
239 dom_pre_idx: usize::MAX,
240 dom_post_idx: 0,
241 lph: usize::MAX,
242 pred: Vec::new(),
243 succ: Vec::new(),
244 }));
245
246 for (p, s) in edges {
247 nodes[s].pred.push(p);
248 nodes[p].succ.push(s);
249 }
250
251 rev_post_order_sort(&mut nodes);
252 calc_dominance(&mut nodes);
253 let has_loop = detect_loops(&mut nodes);
254
255 CFG {
256 has_loop: has_loop,
257 nodes: nodes,
258 }
259 }
260
get(&self, idx: usize) -> Option<&N>261 pub fn get(&self, idx: usize) -> Option<&N> {
262 self.nodes.get(idx).map(|n| &n.node)
263 }
264
get_mut(&mut self, idx: usize) -> Option<&mut N>265 pub fn get_mut(&mut self, idx: usize) -> Option<&mut N> {
266 self.nodes.get_mut(idx).map(|n| &mut n.node)
267 }
268
iter(&self) -> slice::Iter<CFGNode<N>>269 pub fn iter(&self) -> slice::Iter<CFGNode<N>> {
270 self.nodes.iter()
271 }
272
iter_mut(&mut self) -> slice::IterMut<CFGNode<N>>273 pub fn iter_mut(&mut self) -> slice::IterMut<CFGNode<N>> {
274 self.nodes.iter_mut()
275 }
276
len(&self) -> usize277 pub fn len(&self) -> usize {
278 self.nodes.len()
279 }
280
dom_dfs_pre_index(&self, idx: usize) -> usize281 pub fn dom_dfs_pre_index(&self, idx: usize) -> usize {
282 self.nodes[idx].dom_pre_idx
283 }
284
dom_dfs_post_index(&self, idx: usize) -> usize285 pub fn dom_dfs_post_index(&self, idx: usize) -> usize {
286 self.nodes[idx].dom_post_idx
287 }
288
dom_parent_index(&self, idx: usize) -> Option<usize>289 pub fn dom_parent_index(&self, idx: usize) -> Option<usize> {
290 if idx == 0 {
291 None
292 } else {
293 Some(self.nodes[idx].dom)
294 }
295 }
296
dominates(&self, parent: usize, child: usize) -> bool297 pub fn dominates(&self, parent: usize, child: usize) -> bool {
298 // If a block is unreachable, then dom_pre_idx == usize::MAX and
299 // dom_post_idx == 0. This allows us to trivially handle unreachable
300 // blocks here with zero extra work.
301 self.dom_dfs_pre_index(child) >= self.dom_dfs_pre_index(parent)
302 && self.dom_dfs_post_index(child) <= self.dom_dfs_post_index(parent)
303 }
304
has_loop(&self) -> bool305 pub fn has_loop(&self) -> bool {
306 self.has_loop
307 }
308
is_loop_header(&self, idx: usize) -> bool309 pub fn is_loop_header(&self, idx: usize) -> bool {
310 self.nodes[idx].lph == idx
311 }
312
loop_header_index(&self, idx: usize) -> Option<usize>313 pub fn loop_header_index(&self, idx: usize) -> Option<usize> {
314 let lph = self.nodes[idx].lph;
315 if lph == usize::MAX {
316 None
317 } else {
318 debug_assert!(self.is_loop_header(lph));
319 Some(lph)
320 }
321 }
322
succ_indices(&self, idx: usize) -> &[usize]323 pub fn succ_indices(&self, idx: usize) -> &[usize] {
324 &self.nodes[idx].succ[..]
325 }
326
pred_indices(&self, idx: usize) -> &[usize]327 pub fn pred_indices(&self, idx: usize) -> &[usize] {
328 &self.nodes[idx].pred[..]
329 }
330
drain(&mut self) -> impl Iterator<Item = N> + '_331 pub fn drain(&mut self) -> impl Iterator<Item = N> + '_ {
332 self.has_loop = false;
333 self.nodes.drain(..).map(|n| n.node)
334 }
335 }
336
337 impl<N> Index<usize> for CFG<N> {
338 type Output = N;
339
index(&self, idx: usize) -> &N340 fn index(&self, idx: usize) -> &N {
341 &self.nodes[idx].node
342 }
343 }
344
345 impl<N> IndexMut<usize> for CFG<N> {
index_mut(&mut self, idx: usize) -> &mut N346 fn index_mut(&mut self, idx: usize) -> &mut N {
347 &mut self.nodes[idx].node
348 }
349 }
350
351 impl<'a, N> IntoIterator for &'a CFG<N> {
352 type Item = &'a CFGNode<N>;
353 type IntoIter = slice::Iter<'a, CFGNode<N>>;
354
into_iter(self) -> slice::Iter<'a, CFGNode<N>>355 fn into_iter(self) -> slice::Iter<'a, CFGNode<N>> {
356 self.iter()
357 }
358 }
359
360 impl<'a, N> IntoIterator for &'a mut CFG<N> {
361 type Item = &'a mut CFGNode<N>;
362 type IntoIter = slice::IterMut<'a, CFGNode<N>>;
363
into_iter(self) -> slice::IterMut<'a, CFGNode<N>>364 fn into_iter(self) -> slice::IterMut<'a, CFGNode<N>> {
365 self.iter_mut()
366 }
367 }
368
369 pub struct CFGBuilder<K, N> {
370 nodes: Vec<N>,
371 edges: Vec<(K, K)>,
372 key_map: HashMap<K, usize>,
373 }
374
375 impl<K, N> CFGBuilder<K, N> {
new() -> CFGBuilder<K, N>376 pub fn new() -> CFGBuilder<K, N> {
377 CFGBuilder {
378 nodes: Vec::new(),
379 edges: Vec::new(),
380 key_map: HashMap::new(),
381 }
382 }
383 }
384
385 impl<K: Eq + Hash, N> CFGBuilder<K, N> {
add_node(&mut self, k: K, n: N)386 pub fn add_node(&mut self, k: K, n: N) {
387 self.key_map.insert(k, self.nodes.len());
388 self.nodes.push(n);
389 }
390
add_edge(&mut self, s: K, p: K)391 pub fn add_edge(&mut self, s: K, p: K) {
392 self.edges.push((s, p));
393 }
394
as_cfg(mut self) -> CFG<N>395 pub fn as_cfg(mut self) -> CFG<N> {
396 let edges = self.edges.drain(..).map(|(s, p)| {
397 let s = *self.key_map.get(&s).unwrap();
398 let p = *self.key_map.get(&p).unwrap();
399 (s, p)
400 });
401 CFG::from_blocks_edges(self.nodes, edges)
402 }
403 }
404
405 impl<K, N> Default for CFGBuilder<K, N> {
default() -> Self406 fn default() -> Self {
407 CFGBuilder::new()
408 }
409 }
410