charon_lib/transform/control_flow/
merge_goto_chains.rs

1//! # Micro-pass: merge single-origin gotos into their parent and skip over blocks that consist of
2//! only a goto.
3use rustc_hash::FxHashSet as HashSet;
4use std::mem;
5
6use crate::ids::IndexVec;
7use crate::transform::TransformCtx;
8use crate::ullbc_ast::*;
9
10use crate::transform::ctx::UllbcPass;
11
12/// Set of antecedents of a given block. We only care about block ids if there's a single
13/// antecedent.
14enum Antecedents {
15    Zero,
16    One {
17        id: BlockId,
18        /// Whether the antecedent is a goto.
19        is_goto: bool,
20    },
21    Many,
22}
23
24impl Antecedents {
25    fn add(&mut self, id: BlockId, is_goto: bool) {
26        match self {
27            Antecedents::Zero => *self = Antecedents::One { id, is_goto },
28            Antecedents::One { .. } => *self = Antecedents::Many,
29            Antecedents::Many => {}
30        }
31    }
32}
33
34pub struct Transform;
35impl UllbcPass for Transform {
36    fn transform_body(&self, _ctx: &mut TransformCtx, body: &mut ExprBody) {
37        // Compute for each block the set of blocks that points to it.
38        let mut antecedents: IndexVec<BlockId, Antecedents> =
39            body.body.map_ref(|_| Antecedents::Zero);
40        for (block_id, block) in body.body.iter_enumerated() {
41            let is_goto = block.terminator.kind.is_goto();
42            for target in block.targets() {
43                antecedents.get_mut(target).unwrap().add(block_id, is_goto);
44            }
45        }
46        // Merge blocks with a single antecedent into their antecedent.
47        for mut id in body.body.indices() {
48            // Go up the chain to find the first parent into which we can merge.
49            while let Antecedents::One {
50                id: antecedent_id,
51                is_goto: true,
52            } = antecedents[id]
53            {
54                id = antecedent_id;
55            }
56            // While the current block is a straight goto, merge the target block back into this
57            // one.
58            while let source = &body.body[id]
59                && let TerminatorKind::Goto { target } = source.terminator.kind
60                && let Antecedents::One { .. } = antecedents[target]
61                && source.is_cleanup == body.body[target].is_cleanup
62            {
63                antecedents[target] = Antecedents::Zero;
64                let mut target =
65                    mem::replace(&mut body.body[target], BlockData::new_unreachable(false));
66                let source = &mut body.body[id];
67                source.statements.append(&mut target.statements);
68                source.terminator = target.terminator;
69            }
70        }
71        // Skip over trivial gotos.
72        let mut visited = HashSet::default(); // detect and skip loops
73        for id in body.body.indices() {
74            if body.body[id]
75                .targets()
76                .into_iter()
77                .any(|t| body.body[t].as_trivial_goto().is_some())
78            {
79                // Merge any forward goto chains that start here.
80                let mut source =
81                    mem::replace(&mut body.body[id], BlockData::new_unreachable(false));
82                for target_id in source.terminator.targets_mut() {
83                    visited.clear();
84                    visited.insert(id);
85                    while let Some(b) = body.body[*target_id].as_trivial_goto()
86                        && source.is_cleanup == body.body[*target_id].is_cleanup
87                        && visited.insert(*target_id)
88                    {
89                        *target_id = b
90                    }
91                }
92                body.body[id] = source;
93            }
94        }
95    }
96}
charon_lib/transform/control_flow/merge_goto_chains.rs

charon_lib/transform/control_flow/
merge_goto_chains.rs
