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 std::collections::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_indexed() {
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.all_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            {
62                antecedents[target] = Antecedents::Zero;
63                let mut target = mem::replace(&mut body.body[target], BlockData::new_unreachable());
64                let source = &mut body.body[id];
65                source.statements.append(&mut target.statements);
66                source.terminator = target.terminator;
67            }
68        }
69        // Skip over trivial gotos.
70        let mut visited = HashSet::new(); // detect and skip loops
71        for id in body.body.all_indices() {
72            if body.body[id]
73                .targets()
74                .into_iter()
75                .any(|t| body.body[t].as_trivial_goto().is_some())
76            {
77                // Merge any forward goto chains that start here.
78                let mut source = mem::replace(&mut body.body[id], BlockData::new_unreachable());
79                for target_id in source.terminator.targets_mut() {
80                    visited.clear();
81                    visited.insert(id);
82                    while let Some(b) = body.body[*target_id].as_trivial_goto()
83                        && visited.insert(*target_id)
84                    {
85                        *target_id = b
86                    }
87                }
88                body.body[id] = source;
89            }
90        }
91    }
92}
charon_lib/transform/control_flow/merge_goto_chains.rs

charon_lib/transform/control_flow/
merge_goto_chains.rs
