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}