Skip to main content

charon_lib/transform/control_flow/
ullbc_to_llbc.rs

1//! ULLBC to LLBC
2//!
3//! We reconstruct the control-flow in the Unstructured LLBC.
4//!
5//! The reconstruction algorithm is not written to be efficient (its complexity
6//! is probably very bad), but it was not written to be: this is still an early
7//! stage and we want the algorithm to generate the best reconstruction as
8//! possible. We still need to test the algorithm on more interesting examples,
9//! and will consider making it more efficient once it is a bit mature and well
10//! tested.
11//! Also note that we more importantly focus on making the algorithm sound: the
12//! reconstructed program must always be equivalent to the original MIR program,
13//! and the fact that the reconstruction preserves this property must be obvious.
14use itertools::Itertools;
15use petgraph::algo::dijkstra;
16use petgraph::algo::dominators::{Dominators, simple_fast};
17use petgraph::graphmap::DiGraphMap;
18use petgraph::visit::{Dfs, DfsPostOrder, EdgeFiltered, EdgeRef, Walker};
19use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
20use smallvec::SmallVec;
21use std::cmp::Reverse;
22use std::mem;
23
24use crate::ids::IndexVec;
25use crate::llbc_ast::{self as tgt, StatementId};
26use crate::transform::TransformCtx;
27use crate::transform::ctx::TransformPass;
28use crate::ullbc_ast::{self as src, BlockId};
29use crate::utils::{DfsWithPath, ensure_sufficient_stack};
30use crate::{ast::*, register_error};
31
32/// The amount of "flow" reaching a block.
33#[derive(Debug, Default, Copy, Clone)]
34struct Flow(f64);
35
36impl Ord for Flow {
37    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
38        self.0.total_cmp(&other.0)
39    }
40}
41impl PartialOrd for Flow {
42    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
43        Some(self.cmp(other))
44    }
45}
46impl PartialEq for Flow {
47    fn eq(&self, other: &Self) -> bool {
48        self.cmp(other).is_eq()
49    }
50}
51impl Eq for Flow {}
52impl std::ops::AddAssign<Flow> for Flow {
53    fn add_assign(&mut self, other: Flow) {
54        self.0 += other.0;
55    }
56}
57impl Flow {
58    const ZERO: Flow = Flow(0.);
59    const ONE: Flow = Flow(1.);
60    fn divided_by(self, n: usize) -> Flow {
61        Flow(self.0 / (n as f64))
62    }
63}
64
65/// Control-Flow Graph
66type Cfg = DiGraphMap<src::BlockId, (), rustc_hash::FxBuildHasher>;
67
68/// Information precomputed about a function's CFG.
69#[derive(Debug)]
70struct CfgInfo {
71    /// The CFG
72    pub cfg: Cfg,
73    /// The CFG where all the backward edges have been removed. Aka "forward CFG".
74    pub fwd_cfg: Cfg,
75    /// We consider the destination of the backward edges to be loop entries and
76    /// store them here.
77    pub loop_entries: HashSet<src::BlockId>,
78    /// The blocks whose terminators are a switch are stored here.
79    pub switch_blocks: HashSet<src::BlockId>,
80    /// Tree of which nodes dominates which other nodes.
81    #[expect(unused)]
82    pub dominator_tree: Dominators<BlockId>,
83    /// Computed data about each block.
84    pub block_data: IndexVec<BlockId, Box<BlockData>>,
85}
86
87#[derive(Debug)]
88struct BlockData {
89    pub id: BlockId,
90    pub span: Span,
91    /// The (unique) entrypoints of each loop. Unique because we error on irreducible cfgs.
92    pub is_loop_header: bool,
93    /// Whether this block is only reachable by taking an unwind edge.
94    pub is_unwind: bool,
95    /// Whether this block does nothing but return (and possibly deallocate locals).
96    pub is_return: bool,
97    /// Whether this block has multiple incoming control-flow edges in the forward graph.
98    pub is_merge_target: bool,
99    /// Order in a reverse postorder numbering. `None` if the block is unreachable.
100    pub reverse_postorder: Option<u32>,
101    /// Nodes that this block immediately dominates. Sorted by reverse_postorder_id, with largest
102    /// id first.
103    pub immediately_dominates: SmallVec<[BlockId; 2]>,
104    /// The nodes from `immediately_dominates` that are also merge targets. Sorted in the same
105    /// order.
106    pub immediately_dominated_merge_targets: SmallVec<[BlockId; 2]>,
107    /// List of loops inside of which this node is (loops are identified by their header). A node
108    /// is considered inside a loop if it is reachable from the loop header and if it can reach the
109    /// loop header using only the backwards edges into it (i.e. we don't count a path that enters
110    /// the loop header through a forward edge).
111    ///
112    /// Note that we might have to take a backward edge to reach the loop header, e.g.:
113    ///   'a: loop {
114    ///       // ...
115    ///       'b: loop {
116    ///           // ...
117    ///           if true {
118    ///               continue 'a;
119    ///           } else {
120    ///               if true {
121    ///                   break 'a;
122    ///               }
123    ///               // This node has to take two backward edges in order to reach the start of `'a`.
124    ///           }
125    ///       }
126    ///   }
127    ///
128    /// The restriction on backwards edges is for the following case:
129    ///   loop {
130    ///     loop {
131    ///       ..
132    ///     }
133    ///     // Not in inner loop
134    ///   }
135    ///
136    /// This is sorted by path order from the graph root.
137    pub within_loops: SmallVec<[BlockId; 2]>,
138    /// Node from where we can only reach error nodes (panic, etc.)
139    // TODO: track more nicely the set of targets reachable from a node: panic, return, exit loop,
140    // continue loop (this is a partial order).
141    pub only_reach_error: bool,
142    /// List of reachable nodes, with the length of shortest path to them. Includes the current
143    /// node.
144    pub shortest_paths: hashbrown::HashMap<BlockId, usize>,
145    /// Let's say we put a quantity of water equal to 1 on the block, and the water flows downards.
146    /// Whenever there is a branching, the quantity of water gets equally divided between the
147    /// branches. When the control flows join, we put the water back together. The set below
148    /// computes the amount of water received by each descendant of the node.
149    ///
150    /// TODO: there must be a known algorithm which computes this, right?...
151    /// This is exactly this problems:
152    /// <https://stackoverflow.com/questions/78221666/algorithm-for-total-flow-through-weighted-directed-acyclic-graph>
153    /// TODO: the way I compute this is not efficient.
154    pub flow: IndexVec<BlockId, Flow>,
155    /// Reconstructed information about loops and switches.
156    pub exit_info: ExitInfo,
157}
158
159#[derive(Debug, Default, Clone)]
160struct ExitInfo {
161    /// The loop exit
162    loop_exit: Option<src::BlockId>,
163    /// The switch exit.
164    switch_exit: Option<src::BlockId>,
165}
166
167/// Error indicating that the control-flow graph is not reducible. The contained block id is a
168/// block involved in an irreducible subgraph.
169struct Irreducible(BlockId);
170
171impl BlockData {
172    fn new(id: BlockId, data: &ullbc_ast::BlockData, flow: IndexVec<BlockId, Flow>) -> Self {
173        Self {
174            id,
175            span: data.terminator.span,
176            is_loop_header: false,
177            is_unwind: false,
178            is_return: data.is_trivial_return(),
179            is_merge_target: false,
180            reverse_postorder: None,
181            immediately_dominates: Default::default(),
182            immediately_dominated_merge_targets: Default::default(),
183            within_loops: Default::default(),
184            only_reach_error: false,
185            shortest_paths: Default::default(),
186            flow,
187            exit_info: Default::default(),
188        }
189    }
190}
191
192impl CfgInfo {
193    /// Build the CFGs (the "regular" CFG and the CFG without backward edges) and precompute a
194    /// bunch of graph information about the CFG.
195    fn build(ctx: &TransformCtx, body: &src::BodyContents) -> Result<Self, Irreducible> {
196        // The steps in this function follow a precise order, as each step typically requires the
197        // previous one.
198        let start_block = BlockId::ZERO;
199
200        let empty_flow = body.map_ref(|_| Flow::ZERO);
201        let mut block_data: IndexVec<BlockId, _> = body.map_ref_indexed(|id, contents| {
202            Box::new(BlockData::new(id, contents, empty_flow.clone()))
203        });
204
205        // Build the node graph.
206        let mut cfg = Cfg::new();
207        let mut cfg_without_unwind = Cfg::new();
208        for (block_id, block) in body.iter_enumerated() {
209            cfg.add_node(block_id);
210            cfg_without_unwind.add_node(block_id);
211            for tgt in block.targets() {
212                cfg.add_edge(block_id, tgt, ());
213            }
214            for tgt in block.targets_ignoring_unwind() {
215                cfg_without_unwind.add_edge(block_id, tgt, ());
216            }
217        }
218
219        // Compute the dominator tree.
220        let dominator_tree = simple_fast(&cfg, start_block);
221
222        // Compute reverse postorder numbering.
223        for (i, block_id) in DfsPostOrder::new(&cfg, start_block).iter(&cfg).enumerate() {
224            let rev_post_id = body.len() - i;
225            block_data[block_id].reverse_postorder = Some(rev_post_id.try_into().unwrap());
226
227            // Store the dominator tree in `block_data`.
228            if let Some(dominator) = dominator_tree.immediate_dominator(block_id) {
229                block_data[dominator].immediately_dominates.push(block_id);
230            }
231        }
232
233        // Compute the forward graph (without backward edges).
234        let mut fwd_cfg = Cfg::new();
235        let mut loop_entries = HashSet::default();
236        let mut switch_blocks = HashSet::default();
237        for block_id in Dfs::new(&cfg, start_block).iter(&cfg) {
238            fwd_cfg.add_node(block_id);
239
240            if body[block_id].terminator.kind.is_switch() {
241                switch_blocks.insert(block_id);
242            }
243
244            // Iterate over edges into this node (so that we can determine whether this node is a
245            // loop header).
246            let mut incoming_fwd_edges = 0;
247            for from in cfg.neighbors_directed(block_id, petgraph::Direction::Incoming) {
248                // Check if the edge is a backward edge.
249                if block_data[from].reverse_postorder >= block_data[block_id].reverse_postorder {
250                    // This is a backward edge
251                    block_data[block_id].is_loop_header = true;
252                    loop_entries.insert(block_id);
253                    // A cfg is reducible iff the target of every back edge dominates the
254                    // edge's source.
255                    if !dominator_tree.dominators(from).unwrap().contains(&block_id) {
256                        return Err(Irreducible(from));
257                    }
258                } else {
259                    incoming_fwd_edges += 1;
260                    fwd_cfg.add_edge(from, block_id, ());
261                }
262            }
263
264            // Detect merge targets.
265            if incoming_fwd_edges >= 2 {
266                block_data[block_id].is_merge_target = true;
267            }
268        }
269
270        let reachable_without_unwind: HashSet<BlockId> = Dfs::new(&cfg_without_unwind, start_block)
271            .iter(&cfg_without_unwind)
272            .collect();
273
274        // Finish filling in information.
275        for block_id in DfsPostOrder::new(&fwd_cfg, start_block).iter(&fwd_cfg) {
276            let block = &body[block_id];
277            let targets = cfg.neighbors(block_id).collect_vec();
278            let fwd_targets = fwd_cfg.neighbors(block_id).collect_vec();
279
280            // Compute the nodes that are part of unwind paths.
281            block_data[block_id].is_unwind = !reachable_without_unwind.contains(&block_id);
282
283            // Compute the nodes that can only reach error nodes.
284            // The node can only reach error nodes if:
285            // - it is an error node;
286            // - or it has neighbors and they all lead to errors.
287            // Note that if there is a backward edge, `only_reach_error` cannot contain this
288            // node yet. In other words, this does not consider infinite loops as reaching an
289            // error node.
290            if block.terminator.is_error()
291                || (!targets.is_empty()
292                    && targets.iter().all(|&tgt| block_data[tgt].only_reach_error))
293            {
294                block_data[block_id].only_reach_error = true;
295            }
296
297            // Compute the flows between each pair of nodes.
298            let mut flow: IndexVec<src::BlockId, Flow> = mem::take(&mut block_data[block_id].flow);
299            // The flow to self is 1.
300            flow[block_id] = Flow::ONE;
301            // If a block has both regular and unwind targets, don't let the unwind path dilute
302            // the normal-control-flow heuristic used to pick switch exits. Unwind-only subgraphs
303            // still flow through their own targets.
304            let mut flow_targets = fwd_targets
305                .iter()
306                .copied()
307                .filter(|&child| !block_data[child].is_unwind)
308                .collect_vec();
309            if flow_targets.is_empty() {
310                flow_targets = fwd_targets;
311            }
312            // Divide the flow from each child to a given target block by the number of children.
313            // This is a sparse matrix multiplication and could be implemented using a linalg
314            // library.
315            let num_children = flow_targets.len();
316            for child in flow_targets {
317                for grandchild in block_data[child].reachable_including_self() {
318                    // Flow from `child` to `grandchild`
319                    flow[grandchild] += block_data[child].flow[grandchild].divided_by(num_children);
320                }
321            }
322            block_data[block_id].flow = flow;
323
324            // Compute shortest paths to all reachable nodes in the forward graph.
325            block_data[block_id].shortest_paths = dijkstra(&fwd_cfg, block_id, None, |_| 1usize);
326
327            // Fill in the rest of the domination data.
328            let mut dominatees = mem::take(&mut block_data[block_id].immediately_dominates);
329            dominatees.sort_by_key(|&child| block_data[child].reverse_postorder);
330            dominatees.reverse();
331            block_data[block_id].immediately_dominates = dominatees;
332            block_data[block_id].immediately_dominated_merge_targets = block_data[block_id]
333                .immediately_dominates
334                .iter()
335                .copied()
336                .filter(|&child| block_data[child].is_merge_target)
337                .collect();
338        }
339
340        // Fill in the within_loop information. See the docs of `within_loops` to understand what
341        // we're computing.
342        let mut path_dfs = DfsWithPath::new(&cfg, start_block);
343        while let Some(block_id) = path_dfs.next(&cfg) {
344            // Store all the loops on the path to this
345            // node.
346            let mut within_loops: SmallVec<_> = path_dfs
347                .path
348                .iter()
349                .copied()
350                .filter(|&loop_id| block_data[loop_id].is_loop_header)
351                .collect();
352            // The loops that we can reach by taking a single backward edge.
353            let loops_directly_within = within_loops
354                .iter()
355                .copied()
356                .filter(|&loop_header| {
357                    cfg.neighbors_directed(loop_header, petgraph::Direction::Incoming)
358                        .any(|bid| block_data[block_id].shortest_paths.contains_key(&bid))
359                })
360                .collect_vec();
361            // The loops that we can reach by taking any number of backward edges.
362            let loops_indirectly_within: HashSet<_> = loops_directly_within
363                .iter()
364                .copied()
365                .flat_map(|loop_header| &block_data[loop_header].within_loops)
366                .chain(&loops_directly_within)
367                .copied()
368                .collect();
369            within_loops.retain(|id| loops_indirectly_within.contains(id));
370            block_data[block_id].within_loops = within_loops;
371        }
372
373        let mut cfg = CfgInfo {
374            cfg,
375            fwd_cfg,
376            loop_entries,
377            switch_blocks,
378            dominator_tree,
379            block_data,
380        };
381
382        // Pick an exit block for each loop, if we find one.
383        ExitInfo::compute_loop_exits(ctx, &mut cfg);
384
385        // Pick an exit block for each switch, if we find one.
386        ExitInfo::compute_switch_exits(&mut cfg);
387
388        Ok(cfg)
389    }
390
391    fn block_data(&self, block_id: BlockId) -> &BlockData {
392        &self.block_data[block_id]
393    }
394    // fn can_reach(&self, src: BlockId, tgt: BlockId) -> bool {
395    //     self.block_data[src].shortest_paths.contains_key(&tgt)
396    // }
397    fn topo_rank(&self, block_id: BlockId) -> u32 {
398        self.block_data[block_id].reverse_postorder.unwrap()
399    }
400    #[expect(unused)]
401    fn is_backward_edge(&self, src: BlockId, tgt: BlockId) -> bool {
402        self.block_data[src].reverse_postorder >= self.block_data[tgt].reverse_postorder
403            && self.cfg.contains_edge(src, tgt)
404    }
405
406    /// Check if the node is within the given loop.
407    fn is_within_loop(&self, loop_header: src::BlockId, block_id: src::BlockId) -> bool {
408        self.block_data[block_id]
409            .within_loops
410            .contains(&loop_header)
411    }
412
413    /// Check if all paths from `src` to nodes in `target_set` go through `through_node`. If `src`
414    /// is already in `target_set`, we ignore that empty path.
415    fn all_paths_go_through(
416        &self,
417        src: src::BlockId,
418        through_node: src::BlockId,
419        target_set: &HashSet<src::BlockId>,
420    ) -> bool {
421        let graph = EdgeFiltered::from_fn(&self.fwd_cfg, |edge| edge.source() != through_node);
422        !Dfs::new(&graph, src)
423            .iter(&graph)
424            .skip(1) // skip src
425            .any(|bid| target_set.contains(&bid))
426    }
427}
428
429impl BlockData {
430    fn shortest_paths_including_self(&self) -> impl Iterator<Item = (BlockId, usize)> {
431        self.shortest_paths.iter().map(|(bid, d)| (*bid, *d))
432    }
433    fn shortest_paths_excluding_self(&self) -> impl Iterator<Item = (BlockId, usize)> {
434        self.shortest_paths_including_self()
435            .filter(move |&(bid, _)| bid != self.id)
436    }
437    fn reachable_including_self(&self) -> impl Iterator<Item = BlockId> {
438        self.shortest_paths_including_self().map(|(bid, _)| bid)
439    }
440    fn reachable_excluding_self(&self) -> impl Iterator<Item = BlockId> {
441        self.shortest_paths_excluding_self().map(|(bid, _)| bid)
442    }
443    #[expect(unused)]
444    fn can_reach_excluding_self(&self, other: BlockId) -> bool {
445        self.shortest_paths.contains_key(&other) && self.id != other
446    }
447}
448
449/// See [`ExitInfo::compute_loop_exit_ranks`].
450#[derive(Debug, Default, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
451struct LoopExitRank {
452    /// Number of paths we found going to this exit.
453    path_count: usize,
454    /// Distance from the loop header.
455    distance_from_header: Reverse<usize>,
456}
457
458impl ExitInfo {
459    /// Compute the first node on each path that exits the loop.
460    fn compute_loop_exit_starting_points(
461        cfg: &CfgInfo,
462        loop_header: src::BlockId,
463    ) -> Vec<src::BlockId> {
464        let mut loop_exits = Vec::new();
465        // Do a dfs from the loop header while keeping track of the path from the loop header to
466        // the current node.
467        let mut dfs = Dfs::new(&cfg.fwd_cfg, loop_header);
468        while let Some(block_id) = dfs.next(&cfg.fwd_cfg) {
469            // If we've exited all the loops after and including the target one, this node is an
470            // exit node for the target loop.
471            if !cfg.is_within_loop(loop_header, block_id) {
472                loop_exits.push(block_id);
473                // Don't explore any more paths from this node.
474                dfs.discovered.extend(cfg.fwd_cfg.neighbors(block_id));
475            }
476        }
477        loop_exits
478    }
479
480    /// Compute the loop exit candidates along with a rank.
481    ///
482    /// In the simple case, there is one exit node through which all exit paths go. We want to be
483    /// sure to catch that case, and when that's not possible we want to still find a node through
484    /// which a lot of exit paths go.
485    ///
486    /// To do that, we first count for each exit node how many exit paths go through it, and pick
487    /// the node with most occurrences. If there are many such nodes, we pick the one with shortest
488    /// distance from the loop header. Finally if there are still many such nodes, we keep the
489    /// first node found (the order in which we explore the graph is deterministic, and we use an
490    /// insertion-order hash map).
491    ///
492    /// Note that exit candidates will typically be referenced more than once for one loop. This
493    /// comes from the fact that whenever we reach a node outside the current loop, we register
494    /// this node as well as all its children as exit candidates.
495    /// Consider the following example:
496    /// ```text
497    /// while i < max {
498    ///     if cond {
499    ///         break;
500    ///     }
501    ///     s += i;
502    ///     i += 1
503    /// }
504    /// // All the below nodes are exit candidates (each of them is referenced twice)
505    /// s += 1;
506    /// return s;
507    /// ```
508    fn compute_loop_exit_ranks(
509        cfg: &CfgInfo,
510        loop_header: src::BlockId,
511    ) -> SeqHashMap<src::BlockId, LoopExitRank> {
512        let mut loop_exits: SeqHashMap<BlockId, LoopExitRank> = SeqHashMap::new();
513        let header_is_unwind = cfg.block_data[loop_header].is_unwind;
514        for block_id in Self::compute_loop_exit_starting_points(cfg, loop_header) {
515            for bid in cfg.block_data(block_id).reachable_including_self() {
516                let block_data = &cfg.block_data[bid];
517                // We want to force duplication of return-only blocks, so we only count them for the
518                // paths that jump to them directly.
519                if block_data.is_return && bid != block_id {
520                    continue;
521                }
522                // Unwind paths are translated inside the `on_unwind` block of the statement that
523                // unwinds, so we can't `break` to them from a regular loop.
524                if block_data.is_unwind && !header_is_unwind {
525                    continue;
526                }
527                loop_exits
528                    .entry(bid)
529                    .or_insert_with(|| LoopExitRank {
530                        path_count: 0,
531                        distance_from_header: Reverse(
532                            cfg.block_data[loop_header].shortest_paths[&bid],
533                        ),
534                    })
535                    .path_count += 1;
536            }
537        }
538        loop_exits
539    }
540
541    /// A loop exit is any block reachable from the loop header that isn't inside the loop.
542    /// This function choses an exit for every loop. See `compute_loop_exit_ranks` for how we
543    /// select them.
544    ///
545    /// For example:
546    /// ```text
547    /// while ... {
548    ///    ...
549    ///    if ... {
550    ///        // We can't reach the loop entry from here: this is an exit
551    ///        // candidate
552    ///        return;
553    ///    }
554    /// }
555    /// // This is another exit candidate - and this is the one we want to use
556    /// // as the "real" exit...
557    /// ...
558    /// ```
559    ///
560    /// Once we listed all the exit candidates, we find the "best" one for every loop. The best
561    /// exit is the following one:
562    /// - it is the one which is used the most times (note that there can be
563    ///   several candidates which are referenced strictly more than once: see the
564    ///   comment below)
565    /// - if several exits have the same number of occurrences, we choose the one
566    ///   for which we goto the "earliest" (earliest meaning that the goto is close to
567    ///   the loop entry node in the AST). The reason is that all the loops should
568    ///   have an outer if ... then ... else ... which executes the loop body or goes
569    ///   to the exit (note that this is not necessarily the first
570    ///   if ... then ... else ... we find: loop conditions can be arbitrary
571    ///   expressions, containing branchings).
572    ///
573    /// # Several candidates for a loop exit:
574    /// =====================================
575    /// There used to be a sanity check to ensure there are no two different
576    /// candidates with exactly the same number of occurrences and distance from
577    /// the entry of the loop, if the number of occurrences is > 1.
578    ///
579    /// We removed it because it does happen, for instance here (the match
580    /// introduces an `unreachable` node, and it has the same number of
581    /// occurrences and the same distance to the loop entry as the `panic`
582    /// node):
583    ///
584    /// ```text
585    /// pub fn list_nth_mut_loop_pair<'a, T>(
586    ///     mut ls: &'a mut List<T>,
587    ///     mut i: u32,
588    /// ) -> &'a mut T {
589    ///     loop {
590    ///         match ls {
591    ///             List::Nil => {
592    ///                 panic!() // <-- best candidate
593    ///             }
594    ///             List::Cons(x, tl) => {
595    ///                 if i == 0 {
596    ///                     return x;
597    ///                 } else {
598    ///                     ls = tl;
599    ///                     i -= 1;
600    ///                 }
601    ///             }
602    ///             _ => {
603    ///               // Note that Rustc always introduces an unreachable branch after
604    ///               // desugaring matches.
605    ///               unreachable!(), // <-- best candidate
606    ///             }
607    ///         }
608    ///     }
609    /// }
610    /// ```
611    ///
612    /// When this happens we choose an exit candidate whose edges don't necessarily
613    /// lead to an error (above there are none, so we don't choose any exits). Note
614    /// that this last condition is important to prevent loops from being unnecessarily
615    /// nested:
616    ///
617    /// ```text
618    /// pub fn nested_loops_enum(step_out: usize, step_in: usize) -> usize {
619    ///     let mut s = 0;
620    ///
621    ///     for _ in 0..128 { // We don't want this loop to be nested with the loops below
622    ///         s += 1;
623    ///     }
624    ///
625    ///     for _ in 0..(step_out) {
626    ///         for _ in 0..(step_in) {
627    ///             s += 1;
628    ///         }
629    ///     }
630    ///
631    ///     s
632    /// }
633    /// ```
634    fn compute_loop_exits(_ctx: &TransformCtx, cfg: &mut CfgInfo) {
635        for &loop_id in &cfg.loop_entries {
636            // Compute the candidates.
637            let loop_exits: SeqHashMap<BlockId, LoopExitRank> =
638                Self::compute_loop_exit_ranks(cfg, loop_id);
639            // We choose the exit with:
640            // - the most occurrences
641            // - the least total distance (if there are several possibilities)
642            // - doesn't necessarily lead to an error (panic, unreachable)
643            let best_exits: Vec<(BlockId, LoopExitRank)> =
644                loop_exits.into_iter().max_set_by_key(|&(_, rank)| rank);
645            // If there is exactly one best candidate, use it. Otherwise we need to split further.
646            let chosen_exit = match best_exits.into_iter().map(|(bid, _)| bid).exactly_one() {
647                Ok(best_exit) => Some(best_exit),
648                Err(best_exits) => {
649                    // Remove the candidates which only lead to errors (panic or unreachable).
650                    // If there is exactly one candidate we select it, otherwise we do not select any
651                    // exit.
652                    // We don't want to select any exit if we are in the below situation
653                    // (all paths lead to errors). We added a sanity check below to
654                    // catch the situations where there are several exits which don't
655                    // lead to errors.
656                    //
657                    // Example:
658                    // ========
659                    // ```
660                    // loop {
661                    //     match ls {
662                    //         List::Nil => {
663                    //             panic!() // <-- best candidate
664                    //         }
665                    //         List::Cons(x, tl) => {
666                    //             if i == 0 {
667                    //                 return x;
668                    //             } else {
669                    //                 ls = tl;
670                    //                 i -= 1;
671                    //             }
672                    //         }
673                    //         _ => {
674                    //           unreachable!(); // <-- best candidate (Rustc introduces an `unreachable` case)
675                    //         }
676                    //     }
677                    // }
678                    // ```
679                    // The `exactly_one` can fail, see `tests/ui/control-flow/ambiguous-loop-exit.rs`
680                    best_exits
681                        .filter(|&bid| !cfg.block_data[bid].only_reach_error)
682                        .exactly_one()
683                        .ok()
684                }
685            };
686            cfg.block_data[loop_id].exit_info.loop_exit = chosen_exit;
687        }
688    }
689
690    /// Let's consider the following piece of code:
691    /// ```text
692    /// if cond1 { ... } else { ... };
693    /// if cond2 { ... } else { ... };
694    /// ```
695    /// Once converted to MIR, the control-flow is destructured, which means we
696    /// have gotos everywhere. When reconstructing the control-flow, we have
697    /// to be careful about the point where we should join the two branches of
698    /// the first if.
699    /// For instance, if we don't notice they should be joined at some point (i.e,
700    /// whatever the branch we take, there is a moment when we go to the exact
701    /// same place, just before the second if), we might generate code like
702    /// this, with some duplicata:
703    /// ```text
704    /// if cond1 { ...; if cond2 { ... } else { ...} }
705    /// else { ...; if cond2 { ... } else { ...} }
706    /// ```
707    ///
708    /// Such a reconstructed program is valid, but it is definitely non-optimal:
709    /// it is very different from the original program (making it less clean and
710    /// clear), more bloated, and might involve duplicating the proof effort.
711    ///
712    /// For this reason, we need to find the "exit" of the first switch, which is
713    /// the point where the two branches join. Note that this can be a bit tricky,
714    /// because there may be more than two branches (if we do `switch(x) { ... }`),
715    /// and some of them might not join (if they contain a `break`, `panic`,
716    /// `return`, etc.).
717    ///
718    /// In order to compute the switch exits, we simply recursively compute a
719    /// topologically ordered set of "filtered successors" as follows (note
720    /// that we work in the CFG *without* back edges):
721    /// - for a block which doesn't branch (only one successor), the filtered
722    ///   successors is the set of reachable nodes.
723    /// - for a block which branches, we compute the nodes reachable from all
724    ///   the children, and find the "best" intersection between those.
725    ///   Note that we find the "best" intersection (a pair of branches which
726    ///   maximize the intersection of filtered successors) because some branches
727    ///   might never join the control-flow of the other branches, if they contain
728    ///   a `break`, `return`, `panic`, etc., like here:
729    ///   ```text
730    ///   if b { x = 3; } { return; }
731    ///   y += x;
732    ///   ...
733    ///   ```
734    /// Note that with nested switches, the branches of the inner switches might
735    /// goto the exits of the outer switches: for this reason, we give precedence
736    /// to the outer switches.
737    fn compute_switch_exits(cfg: &mut CfgInfo) {
738        // We need to give precedence to the outer switches: we thus iterate
739        // over the switch blocks in topological order.
740        let mut exits_set = HashSet::default();
741        for bid in cfg
742            .switch_blocks
743            .iter()
744            .copied()
745            .sorted_unstable_by_key(|&bid| (cfg.topo_rank(bid), bid))
746        {
747            let block_data = &cfg.block_data[bid];
748            // Find the best successor: this is the node with the highest flow, and the lowest
749            // topological rank. If several nodes have the same flow, we want to take the highest
750            // one in the hierarchy: hence the use of the topological rank.
751            //
752            // Ex.:
753            // ```text
754            // A  -- we start here
755            // |
756            // |---------------------------------------
757            // |            |            |            |
758            // B:(0.25,-1)  C:(0.25,-2)  D:(0.25,-3)  E:(0.25,-4)
759            // |            |            |
760            // |--------------------------
761            // |
762            // F:(0.75,-5)
763            // |
764            // |
765            // G:(0.75,-6)
766            // ```
767            // The "best" node (with the highest (flow, rank) in the graph above is F.
768            // If the switch is inside a loop, we also only consider exists that are inside that
769            // same loop. There must be one, otherwise the switch entry would not be inside the
770            // loop.
771            let current_loop = block_data.within_loops.last().copied();
772            let best_exit: Option<BlockId> = block_data
773                .reachable_excluding_self()
774                .filter(|&b| !cfg.block_data[b].is_return)
775                .filter(|&b| {
776                    current_loop.is_none_or(|current_loop| cfg.is_within_loop(current_loop, b))
777                })
778                .max_by_key(|&id| {
779                    let is_unwind_block = Reverse(cfg.block_data[id].is_unwind);
780                    let flow = &block_data.flow[id];
781                    let rank = Reverse(cfg.topo_rank(id));
782                    ((is_unwind_block, flow, rank), id)
783                });
784            // We have an exit candidate: we first check that it was not already taken by an
785            // external switch.
786            //
787            // We then check that we can't reach the exit of an external switch from one of the
788            // branches, without going through the exit candidate. We do this by simply checking
789            // that we can't reach any of the exits of outer switches.
790            //
791            // The reason is that it can lead to code like the following:
792            // ```
793            // if ... { // if #1
794            //   if ... { // if #2
795            //     ...
796            //     // here, we have a `goto b1`, where b1 is the exit
797            //     // of if #2: we thus stop translating the blocks.
798            //   }
799            //   else {
800            //     ...
801            //     // here, we have a `goto b2`, where b2 is the exit
802            //     // of if #1: we thus stop translating the blocks.
803            //   }
804            //   // We insert code for the block b1 here (which is the exit of
805            //   // the exit of if #2). However, this block should only
806            //   // be executed in the branch "then" of the if #2, not in
807            //   // the branch "else".
808            //   ...
809            // }
810            // else {
811            //   ...
812            // }
813            // ```
814            if let Some(exit_id) = best_exit
815                && !exits_set.contains(&exit_id)
816                && cfg.all_paths_go_through(bid, exit_id, &exits_set)
817            {
818                exits_set.insert(exit_id);
819                cfg.block_data[bid].exit_info.switch_exit = Some(exit_id);
820            }
821        }
822    }
823}
824
825/// Iter over the last non-switch statements that may be executed on any branch of this block.
826/// Skips over `Nop`s.
827fn iter_tail_statements(block: &mut tgt::Block, f: &mut impl FnMut(&mut tgt::Statement)) {
828    let Some(st) = block
829        .statements
830        .iter_mut()
831        .rev()
832        .find(|st| !st.kind.is_nop())
833    else {
834        return;
835    };
836    if let tgt::StatementKind::Switch { branches, .. } = &mut st.kind {
837        for block in branches {
838            iter_tail_statements(block, f);
839        }
840    } else {
841        f(st)
842    };
843}
844
845type Depth = usize;
846
847#[derive(Debug, Copy, Clone)]
848enum SpecialJumpKind {
849    /// This block can be reached by a `continue` to the given depth.
850    LoopContinue(Depth),
851    /// This block can be reached by a `break` to the given depth. This comes from a loop.
852    LoopBreak(Depth),
853    /// This block can be reached by a `break` to the given depth. This is a `loop` context
854    /// introduced only for forward jumps.
855    ForwardBreak(Depth),
856    /// This block can be reached by doing nothing as this is the next block that will be
857    /// translated. Only applies if this block is at the top of the stack.
858    NextBlock,
859}
860
861#[derive(Copy, Clone)]
862struct SpecialJump {
863    /// The relevant block.
864    target_block: BlockId,
865    /// How to translate a jump to the target block.
866    kind: SpecialJumpKind,
867}
868
869impl SpecialJump {
870    fn new(target_block: BlockId, kind: SpecialJumpKind) -> Self {
871        Self { target_block, kind }
872    }
873}
874
875impl std::fmt::Debug for SpecialJump {
876    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
877        write!(f, "SpecialJump({}, {:?})", self.target_block, self.kind)
878    }
879}
880
881/// How to handle blocks reachable from multiple branches.
882enum ReconstructMode {
883    /// Duplicate blocks reachable from multiple branches.
884    Duplicate,
885    /// Insert loops for the purpose of breaking forward to them to implement DAG-like control-flow
886    /// without duplicating blocks.
887    /// Based on the algorithm from "Beyond Relooper" (https://dl.acm.org/doi/10.1145/3547621).
888    ForwardBreak,
889}
890
891struct ReconstructCtx<'a> {
892    cfg: CfgInfo,
893    body: &'a src::ExprBody,
894    /// The depth of `loop` contexts we may `break`/`continue` to.
895    break_context_depth: Depth,
896    /// Stack of block ids that should be translated to special jumps (`break`/`continue`/do
897    /// nothing) in the current context.
898    /// The block where control-flow continues naturally after this block is kept at the top of the
899    /// stack.
900    special_jump_stack: Vec<SpecialJump>,
901    mode: ReconstructMode,
902}
903
904impl<'a> ReconstructCtx<'a> {
905    fn build(ctx: &TransformCtx, src_body: &'a src::ExprBody) -> Result<Self, Irreducible> {
906        // Compute all sorts of graph-related information about the control-flow graph, including
907        // reachability, the dominator tree, loop entries, and loop/switch exits.
908        let cfg = CfgInfo::build(ctx, &src_body.body)?;
909
910        // Translate the body by reconstructing the loops and the
911        // conditional branchings.
912        let allow_duplication = !ctx.options.no_code_duplication;
913        Ok(ReconstructCtx {
914            cfg,
915            body: src_body,
916            break_context_depth: 0,
917            special_jump_stack: Vec::new(),
918            mode: if allow_duplication {
919                ReconstructMode::Duplicate
920            } else {
921                ReconstructMode::ForwardBreak
922            },
923        })
924    }
925
926    fn translate_statement(&self, st: &src::Statement) -> tgt::Statement {
927        let span = st.span;
928        let kind = match st.kind.clone() {
929            src::StatementKind::Assign(place, rvalue) => tgt::StatementKind::Assign(place, rvalue),
930            src::StatementKind::SetDiscriminant(place, variant_id) => {
931                tgt::StatementKind::SetDiscriminant(place, variant_id)
932            }
933            src::StatementKind::StorageLive(var_id) => tgt::StatementKind::StorageLive(var_id),
934            src::StatementKind::StorageDead(var_id) => tgt::StatementKind::StorageDead(var_id),
935            src::StatementKind::Assert { assert, on_failure } => tgt::StatementKind::Assert {
936                assert,
937                on_failure: on_failure.clone(),
938                on_unwind: tgt::Statement::new(span, tgt::StatementKind::UnwindResume).into_block(),
939            },
940            src::StatementKind::PlaceMention(place) => tgt::StatementKind::PlaceMention(place),
941            src::StatementKind::Borrowck(statement) => tgt::StatementKind::Borrowck(statement),
942            src::StatementKind::Nop => tgt::StatementKind::Nop,
943        };
944        let mut translated = tgt::Statement::new(span, kind);
945        translated.comments_before = st.comments_before.clone();
946        translated
947    }
948
949    /// Translate a jump to the given block. The span is used to create the jump statement, if any.
950    #[tracing::instrument(skip(self), ret, fields(stack = ?self.special_jump_stack))]
951    fn translate_jump(&mut self, span: Span, target_block: src::BlockId) -> tgt::Block {
952        match self
953            .special_jump_stack
954            .iter()
955            .rev()
956            .enumerate()
957            .find(|(_, j)| j.target_block == target_block)
958        {
959            Some((i, jump_target)) => {
960                let mk_block = |kind| tgt::Statement::new(span, kind).into_block();
961                match jump_target.kind {
962                    // The top of the stack is where control-flow goes naturally, no need to add a
963                    // `break`/`continue`. We only do that in `ForwardBreak` mode to avoid breaking aeneas.
964                    SpecialJumpKind::LoopContinue(_)
965                    | SpecialJumpKind::ForwardBreak(_)
966                    | SpecialJumpKind::NextBlock
967                        if i == 0 && matches!(self.mode, ReconstructMode::ForwardBreak) =>
968                    {
969                        mk_block(tgt::StatementKind::Nop)
970                    }
971                    SpecialJumpKind::LoopContinue(depth) => mk_block(tgt::StatementKind::Continue(
972                        self.break_context_depth - depth,
973                    )),
974                    SpecialJumpKind::ForwardBreak(depth) | SpecialJumpKind::LoopBreak(depth) => {
975                        mk_block(tgt::StatementKind::Break(self.break_context_depth - depth))
976                    }
977                    SpecialJumpKind::NextBlock if i == 0 => mk_block(tgt::StatementKind::Nop),
978                    // Translate the block without a jump.
979                    SpecialJumpKind::NextBlock => self.translate_block(target_block),
980                }
981            }
982            // Translate the block without a jump.
983            None => self.translate_block(target_block),
984        }
985    }
986
987    fn translate_terminator(&mut self, terminator: &src::Terminator) -> tgt::Block {
988        let src_span = terminator.span;
989
990        match &terminator.kind {
991            src::TerminatorKind::Panic { call, on_unwind } => {
992                let on_unwind = self.translate_block(*on_unwind);
993                tgt::Statement::new(
994                    src_span,
995                    tgt::StatementKind::Panic {
996                        call: call.clone(),
997                        on_unwind,
998                    },
999                )
1000                .into_block()
1001            }
1002            src::TerminatorKind::UndefinedBehavior => {
1003                tgt::Statement::new(src_span, tgt::StatementKind::UndefinedBehavior).into_block()
1004            }
1005            src::TerminatorKind::UnwindTerminate(reason, fun_ref) => tgt::Statement::new(
1006                src_span,
1007                tgt::StatementKind::UnwindTerminate(*reason, fun_ref.clone()),
1008            )
1009            .into_block(),
1010            src::TerminatorKind::Return => {
1011                tgt::Statement::new(src_span, tgt::StatementKind::Return).into_block()
1012            }
1013            src::TerminatorKind::UnwindResume => {
1014                tgt::Statement::new(src_span, tgt::StatementKind::UnwindResume).into_block()
1015            }
1016            src::TerminatorKind::Call {
1017                call,
1018                dest,
1019                target,
1020                on_unwind,
1021            } => {
1022                let on_unwind = self.translate_block(*on_unwind);
1023                let st = tgt::Statement::new(
1024                    src_span,
1025                    tgt::StatementKind::Call {
1026                        call: call.clone(),
1027                        dest: dest.clone(),
1028                        on_unwind,
1029                    },
1030                );
1031                let mut block = self.translate_jump(terminator.span, *target);
1032                block.statements.insert(0, st);
1033                block
1034            }
1035            src::TerminatorKind::Drop {
1036                kind,
1037                place,
1038                fn_ptr,
1039                target,
1040                on_unwind,
1041            } => {
1042                let on_unwind = self.translate_block(*on_unwind);
1043                let st = tgt::Statement::new(
1044                    src_span,
1045                    tgt::StatementKind::Drop {
1046                        place: place.clone(),
1047                        fn_ptr: fn_ptr.clone(),
1048                        kind: *kind,
1049                        on_unwind,
1050                    },
1051                );
1052                let mut block = self.translate_jump(terminator.span, *target);
1053                block.statements.insert(0, st);
1054                block
1055            }
1056            src::TerminatorKind::DropEmptyBox {
1057                place,
1058                target,
1059                on_unwind,
1060            } => {
1061                let on_unwind = self.translate_block(*on_unwind);
1062                let st = tgt::Statement::new(
1063                    src_span,
1064                    tgt::StatementKind::DropEmptyBox {
1065                        place: place.clone(),
1066                        on_unwind,
1067                    },
1068                );
1069                let mut block = self.translate_jump(terminator.span, *target);
1070                block.statements.insert(0, st);
1071                block
1072            }
1073            src::TerminatorKind::Assert {
1074                assert,
1075                target,
1076                on_unwind,
1077            } => {
1078                let on_unwind = self.translate_block(*on_unwind);
1079                let st = tgt::StatementKind::Assert {
1080                    assert: assert.clone(),
1081                    on_failure: AbortKind::Panic,
1082                    on_unwind,
1083                };
1084                let target = self.translate_jump(terminator.span, *target);
1085                tgt::Statement::new(src_span, st).into_block().merge(target)
1086            }
1087            src::TerminatorKind::InlineAsm {
1088                asm,
1089                fallthrough,
1090                labels,
1091                on_unwind,
1092            } => {
1093                let fallthrough =
1094                    fallthrough.map(|target| self.translate_jump(terminator.span, target));
1095                let labels = labels.map_ref(|target| self.translate_jump(terminator.span, *target));
1096                let on_unwind = self.translate_block(*on_unwind);
1097                let st = tgt::StatementKind::InlineAsm {
1098                    asm: asm.clone(),
1099                    fallthrough,
1100                    labels,
1101                    on_unwind,
1102                };
1103                tgt::Statement::new(src_span, st).into_block()
1104            }
1105            src::TerminatorKind::Goto { target } => self.translate_jump(terminator.span, *target),
1106            src::TerminatorKind::Switch { data, branches } => {
1107                let branches =
1108                    branches.map_ref(|target| self.translate_jump(terminator.span, *target));
1109
1110                // Return
1111                let span = combine_span_iter(branches.iter().map(|branch| &branch.span));
1112                let span = combine_span(&src_span, &span);
1113                let st = tgt::StatementKind::Switch {
1114                    data: data.clone(),
1115                    branches,
1116                };
1117                tgt::Statement::new(span, st).into_block()
1118            }
1119        }
1120    }
1121
1122    /// Translate just the block statements and terminator.
1123    fn translate_block_itself(&mut self, block_id: BlockId) -> tgt::Block {
1124        let block = &self.body.body[block_id];
1125        // Translate the statements inside the block
1126        let statements = block
1127            .statements
1128            .iter()
1129            .map(|st| self.translate_statement(st))
1130            .collect_vec();
1131        // Translate the terminator.
1132        let terminator = self.translate_terminator(&block.terminator);
1133        // Prepend the statements to the terminator.
1134        if let Some(st) = tgt::Block::from_seq(statements) {
1135            st.merge(terminator)
1136        } else {
1137            terminator
1138        }
1139    }
1140
1141    /// Translate a block including surrounding control-flow like looping.
1142    #[tracing::instrument(skip(self), fields(stack = ?self.special_jump_stack))]
1143    fn translate_block(&mut self, block_id: src::BlockId) -> tgt::Block {
1144        ensure_sufficient_stack(|| self.translate_block_inner(block_id))
1145    }
1146    fn translate_block_inner(&mut self, block_id: src::BlockId) -> tgt::Block {
1147        // Some of the blocks we might jump to inside this tree can't be translated as normal
1148        // blocks: the loop backward edges must become `continue`s and the merge nodes may need
1149        // some care if we're jumping to them from distant locations.
1150        // For this purpose, we push to the `special_jump_stack` the block ids that must be
1151        // translated specially. In `translate_jump` we check the stack. At the end of this
1152        // function we restore the stack to its previous state.
1153        let old_context_depth = self.special_jump_stack.len();
1154        let block_data = &self.cfg.block_data[block_id];
1155        let span = block_data.span;
1156
1157        // Catch jumps to the loop header or loop exit.
1158        if block_data.is_loop_header {
1159            self.break_context_depth += 1;
1160            if let Some(exit_id) = block_data.exit_info.loop_exit {
1161                self.special_jump_stack.push(SpecialJump::new(
1162                    exit_id,
1163                    SpecialJumpKind::LoopBreak(self.break_context_depth),
1164                ));
1165            }
1166            // Put the next block at the top of the stack.
1167            self.special_jump_stack.push(SpecialJump::new(
1168                block_id,
1169                SpecialJumpKind::LoopContinue(self.break_context_depth),
1170            ));
1171        }
1172
1173        // Catch jumps to a merge node.
1174        let merge_children = &block_data.immediately_dominated_merge_targets;
1175        if let ReconstructMode::ForwardBreak = self.mode {
1176            // We support forward-jumps using `break`
1177            // The child with highest postorder numbering is nested outermost in this scheme.
1178            for &child in merge_children {
1179                self.break_context_depth += 1;
1180                self.special_jump_stack.push(SpecialJump::new(
1181                    child,
1182                    SpecialJumpKind::ForwardBreak(self.break_context_depth),
1183                ));
1184            }
1185        }
1186
1187        if let Some(bid) = block_data.exit_info.switch_exit
1188            && !block_data.is_loop_header
1189            && !(matches!(self.mode, ReconstructMode::ForwardBreak)
1190                && merge_children.contains(&bid))
1191        {
1192            // Move some code that would be inside one or several switch branches to be after the
1193            // switch intead.
1194            self.special_jump_stack
1195                .push(SpecialJump::new(bid, SpecialJumpKind::NextBlock));
1196        }
1197
1198        // Translate this block. Any jumps to a loop header or a merge node will be replaced with
1199        // `continue`/`break`.
1200        let mut block = self.translate_block_itself(block_id);
1201
1202        // Reset the state to what it was previously, and translate what remains.
1203        let new_statement = move |kind| tgt::Statement::new(block.span, kind);
1204        while self.special_jump_stack.len() > old_context_depth {
1205            let special_jump = self.special_jump_stack.pop().unwrap();
1206            match &special_jump.kind {
1207                SpecialJumpKind::LoopContinue(_) => {
1208                    self.break_context_depth -= 1;
1209                    if let ReconstructMode::ForwardBreak = self.mode {
1210                        // We add `continue` at the end for users that don't know that the default
1211                        // behavior at the end of a loop block is `continue`. Not needed for
1212                        // `Duplicate` mode because we use explicit `continue`s there. TODO: clean
1213                        // that up.
1214                        block
1215                            .statements
1216                            .push(new_statement(tgt::StatementKind::Continue(0)));
1217                    }
1218                    block = new_statement(tgt::StatementKind::Loop(block)).into_block();
1219                }
1220                SpecialJumpKind::ForwardBreak(_) => {
1221                    self.break_context_depth -= 1;
1222                    // Remove unneeded `break`s in branches leading up to that final one.
1223                    iter_tail_statements(&mut block, &mut |st| {
1224                        if matches!(st.kind, tgt::StatementKind::Break(0)) {
1225                            st.kind = tgt::StatementKind::Nop;
1226                        }
1227                    });
1228                    // We add a `loop { ...; break }` so that we can use `break` to jump forward.
1229                    block
1230                        .statements
1231                        .push(new_statement(tgt::StatementKind::Break(0)));
1232                    block = new_statement(tgt::StatementKind::Loop(block)).into_block();
1233                    // We must translate the merge nodes after the block used for forward jumps to
1234                    // them.
1235                    let next_block = self.translate_jump(span, special_jump.target_block);
1236                    block = block.merge(next_block);
1237                }
1238                SpecialJumpKind::NextBlock | SpecialJumpKind::LoopBreak(..) => {
1239                    let next_block = self.translate_jump(span, special_jump.target_block);
1240                    block = block.merge(next_block);
1241                }
1242            }
1243        }
1244        block
1245    }
1246}
1247
1248fn remove_useless_jump_blocks(body: &mut tgt::ExprBody) {
1249    use tgt::StatementKind;
1250    #[derive(Default)]
1251    struct Count {
1252        continue_count: u32,
1253        break_count: u32,
1254    }
1255    #[derive(Default, Visitor)]
1256    struct CountJumpsVisitor {
1257        counts: HashMap<StatementId, Count>,
1258        loop_stack: Vec<StatementId>,
1259    }
1260    #[derive(Visitor)]
1261    struct RemoveUselessJumpsVisitor {
1262        counts: HashMap<StatementId, Count>,
1263        /// For every loop we encounter, whether we're keeping it or removing it.
1264        loop_stack: Vec<bool>,
1265    }
1266
1267    impl VisitBodyMut for CountJumpsVisitor {
1268        fn visit_llbc_statement(&mut self, st: &mut tgt::Statement) -> ControlFlow<Self::Break> {
1269            if let StatementKind::Loop(_) = &st.kind {
1270                self.loop_stack.push(st.id);
1271            }
1272            match &st.kind {
1273                StatementKind::Break(depth) => {
1274                    let loop_id = self.loop_stack[self.loop_stack.len() - 1 - depth];
1275                    self.counts.entry(loop_id).or_default().break_count += 1;
1276                }
1277                StatementKind::Continue(depth) => {
1278                    let loop_id = self.loop_stack[self.loop_stack.len() - 1 - depth];
1279                    self.counts.entry(loop_id).or_default().continue_count += 1;
1280                }
1281                _ => {}
1282            }
1283            self.visit_inner(st)?;
1284            if let StatementKind::Loop(_) = &st.kind {
1285                self.loop_stack.pop();
1286            }
1287            ControlFlow::Continue(())
1288        }
1289    }
1290
1291    impl VisitBodyMut for RemoveUselessJumpsVisitor {
1292        fn visit_llbc_block(&mut self, block: &mut tgt::Block) -> ControlFlow<Self::Break> {
1293            for mut st in mem::take(&mut block.statements) {
1294                if let tgt::StatementKind::Loop(block) = &mut st.kind {
1295                    let counts = &self.counts[&st.id];
1296                    let remove = counts.continue_count == 0
1297                        && counts.break_count == 1
1298                        && matches!(
1299                            block.statements.last().unwrap().kind,
1300                            StatementKind::Break(0)
1301                        );
1302                    self.loop_stack.push(!remove);
1303                }
1304                self.visit(&mut st)?;
1305                if st.kind.is_loop() && !self.loop_stack.pop().unwrap() {
1306                    // Remove the loop.
1307                    let StatementKind::Loop(mut inner_block) = st.kind else {
1308                        unreachable!()
1309                    };
1310                    inner_block.statements.last_mut().unwrap().kind = StatementKind::Nop;
1311                    block.statements.extend(inner_block.statements);
1312                } else {
1313                    block.statements.push(st);
1314                }
1315            }
1316            ControlFlow::Continue(())
1317        }
1318        fn enter_llbc_statement(&mut self, st: &mut tgt::Statement) {
1319            match &st.kind {
1320                StatementKind::Break(depth) => {
1321                    let new_depth = self.loop_stack[self.loop_stack.len() - depth..]
1322                        .iter()
1323                        .filter(|&&keep| keep)
1324                        .count();
1325                    st.kind = StatementKind::Break(new_depth);
1326                }
1327                StatementKind::Continue(depth) => {
1328                    let new_depth = self.loop_stack[self.loop_stack.len() - depth..]
1329                        .iter()
1330                        .filter(|&&keep| keep)
1331                        .count();
1332                    st.kind = StatementKind::Continue(new_depth);
1333                }
1334                _ => {}
1335            }
1336        }
1337    }
1338
1339    let mut v = CountJumpsVisitor::default();
1340    body.body.drive_body_mut(&mut v);
1341    let mut v = RemoveUselessJumpsVisitor {
1342        counts: v.counts,
1343        loop_stack: Default::default(),
1344    };
1345    body.body.drive_body_mut(&mut v);
1346}
1347
1348fn translate_body(ctx: &mut TransformCtx, body: &mut Body) {
1349    use Body::{Structured, Unstructured};
1350    let Unstructured(src_body) = body else {
1351        panic!("Called `ullbc_to_llbc` on an already restructured body")
1352    };
1353    trace!("About to translate to ullbc: {:?}", src_body.span);
1354    // Report the time spent per body size, since this pass is superlinear in the number of blocks.
1355    let _guard = crate::timing::scope_lazy("ullbc_to_llbc-body", || {
1356        format!(
1357            "{:05} blocks or less",
1358            src_body.body.len().next_power_of_two()
1359        )
1360    });
1361
1362    // Calculate info about the graph and heuristically determine loop and switch exit blocks.
1363    let start_block = BlockId::ZERO;
1364    let mut ctx = match ReconstructCtx::build(ctx, src_body) {
1365        Ok(ctx) => ctx,
1366        Err(Irreducible(bid)) => {
1367            let span = src_body.body[bid].terminator.span;
1368            register_error!(
1369                ctx,
1370                span,
1371                "the control-flow graph of this function is not reducible"
1372            );
1373            panic!("can't reconstruct irreducible control-flow")
1374        }
1375    };
1376    // Translate the blocks using the computed data.
1377    let tgt_body = ctx.translate_block(start_block);
1378
1379    let mut tgt_body = tgt::ExprBody {
1380        span: src_body.span,
1381        locals: src_body.locals.clone(),
1382        bound_body_regions: src_body.bound_body_regions,
1383        body: tgt_body,
1384        comments: src_body.comments.clone(),
1385    };
1386    remove_useless_jump_blocks(&mut tgt_body);
1387
1388    *body = Structured(tgt_body);
1389}
1390
1391pub struct Transform;
1392impl TransformPass for Transform {
1393    fn transform_ctx(&self, ctx: &mut TransformCtx) {
1394        // Translate the bodies one at a time.
1395        ctx.for_each_body(|ctx, body| {
1396            translate_body(ctx, body);
1397        });
1398    }
1399}