Struct ExitInfo 

struct ExitInfo {
    loop_exit: Option<BlockId>,
    switch_exit: Option<BlockId>,
}

Fields

loop_exit: Option<BlockId>

The loop exit

switch_exit: Option<BlockId>

The switch exit.

Implementations

impl ExitInfo

fn compute_loop_exit_starting_points( cfg: &CfgInfo<'_>, loop_header: BlockId, ) -> Vec<BlockId>

Compute the first node on each path that exits the loop.

fn compute_loop_exit_ranks( cfg: &CfgInfo<'_>, loop_header: BlockId, ) -> SeqHashMap<BlockId, LoopExitRank>

Compute the loop exit candidates along with a rank.

In the simple case, there is one exit node through which all exit paths go. We want to be sure to catch that case, and when that’s not possible we want to still find a node through which a lot of exit paths go.

To do that, we first count for each exit node how many exit paths go through it, and pick the node with most occurrences. If there are many such nodes, we pick the one with shortest distance from the loop header. Finally if there are still many such nodes, we keep the first node found (the order in which we explore the graph is deterministic, and we use an insertion-order hash map).

Note that exit candidates will typically be referenced more than once for one loop. This comes from the fact that whenever we reach a node outside the current loop, we register this node as well as all its children as exit candidates. Consider the following example:

while i < max {
    if cond {
        break;
    }
    s += i;
    i += 1
}
// All the below nodes are exit candidates (each of them is referenced twice)
s += 1;
return s;

fn compute_loop_exits(ctx: &TransformCtx, cfg: &mut CfgInfo<'_>)

A loop exit is any block reachable from the loop header that isn’t inside the loop. This function choses an exit for every loop. See compute_loop_exit_ranks for how we select them.

For example:

while ... {
   ...
   if ... {
       // We can't reach the loop entry from here: this is an exit
       // candidate
       return;
   }
}
// This is another exit candidate - and this is the one we want to use
// as the "real" exit...
...

Once we listed all the exit candidates, we find the “best” one for every loop. The best exit is the following one:

• it is the one which is used the most times (note that there can be several candidates which are referenced strictly more than once: see the comment below)
• if several exits have the same number of occurrences, we choose the one for which we goto the “earliest” (earliest meaning that the goto is close to the loop entry node in the AST). The reason is that all the loops should have an outer if … then … else … which executes the loop body or goes to the exit (note that this is not necessarily the first if … then … else … we find: loop conditions can be arbitrary expressions, containing branchings).

Several candidates for a loop exit:

===================================== There used to be a sanity check to ensure there are no two different candidates with exactly the same number of occurrences and distance from the entry of the loop, if the number of occurrences is > 1.

We removed it because it does happen, for instance here (the match introduces an unreachable node, and it has the same number of occurrences and the same distance to the loop entry as the panic node):

pub fn list_nth_mut_loop_pair<'a, T>(
    mut ls: &'a mut List<T>,
    mut i: u32,
) -> &'a mut T {
    loop {
        match ls {
            List::Nil => {
                panic!() // <-- best candidate
            }
            List::Cons(x, tl) => {
                if i == 0 {
                    return x;
                } else {
                    ls = tl;
                    i -= 1;
                }
            }
            _ => {
              // Note that Rustc always introduces an unreachable branch after
              // desugaring matches.
              unreachable!(), // <-- best candidate
            }
        }
    }
}

When this happens we choose an exit candidate whose edges don’t necessarily lead to an error (above there are none, so we don’t choose any exits). Note that this last condition is important to prevent loops from being unnecessarily nested:

pub fn nested_loops_enum(step_out: usize, step_in: usize) -> usize {
    let mut s = 0;

    for _ in 0..128 { // We don't want this loop to be nested with the loops below
        s += 1;
    }

    for _ in 0..(step_out) {
        for _ in 0..(step_in) {
            s += 1;
        }
    }

    s
}

fn compute_switch_exits(cfg: &mut CfgInfo<'_>)

Let’s consider the following piece of code:

if cond1 { ... } else { ... };
if cond2 { ... } else { ... };

Once converted to MIR, the control-flow is destructured, which means we have gotos everywhere. When reconstructing the control-flow, we have to be careful about the point where we should join the two branches of the first if. For instance, if we don’t notice they should be joined at some point (i.e, whatever the branch we take, there is a moment when we go to the exact same place, just before the second if), we might generate code like this, with some duplicata:

if cond1 { ...; if cond2 { ... } else { ...} }
else { ...; if cond2 { ... } else { ...} }

Such a reconstructed program is valid, but it is definitely non-optimal: it is very different from the original program (making it less clean and clear), more bloated, and might involve duplicating the proof effort.

For this reason, we need to find the “exit” of the first switch, which is the point where the two branches join. Note that this can be a bit tricky, because there may be more than two branches (if we do switch(x) { ... }), and some of them might not join (if they contain a break, panic, return, etc.).

In order to compute the switch exits, we simply recursively compute a topologically ordered set of “filtered successors” as follows (note that we work in the CFG without back edges):

• for a block which doesn’t branch (only one successor), the filtered successors is the set of reachable nodes.
• for a block which branches, we compute the nodes reachable from all the children, and find the “best” intersection between those. Note that we find the “best” intersection (a pair of branches which maximize the intersection of filtered successors) because some branches might never join the control-flow of the other branches, if they contain a break, return, panic, etc., like here:

  if b { x = 3; } { return; }
  y += x;
  ...

Note that with nested switches, the branches of the inner switches might goto the exits of the outer switches: for this reason, we give precedence to the outer switches.

Trait Implementations

impl Clone for ExitInfo

fn clone(&self) -> ExitInfo

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ExitInfo

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for ExitInfo

fn default() -> ExitInfo

Returns the “default value” for a type.