Struct ExitsInfo 

struct ExitsInfo {
    exits: Vector<BlockId, ExitInfo>,
}

The exits of a graph

Fields

exits: Vector<BlockId, ExitInfo>

Implementations

impl ExitsInfo

fn loop_entry_is_reachable_from_inner( cfg: &CfgInfo, loop_entry: BlockId, block_id: BlockId, ) -> bool

Check if a loop entry is reachable from a node, in a graph where we remove the backward edges going directly to the loop entry.

If the loop entry is not reachable, it means that:

• the loop entry is not reachable at all
• or it is only reachable through an outer loop

The starting node should be a (transitive) child of the loop entry. We use this to find candidates for loop exits.

fn filter_loop_parents( cfg: &CfgInfo, parent_loops: &Vec<(BlockId, usize)>, block_id: BlockId, ) -> Option<FilteredLoopParents>

fn can_reach_outer_exit( cfg: &CfgInfo, outer_exits: &HashSet<BlockId>, start_bid: BlockId, exit_candidate: BlockId, ) -> bool

Auxiliary helper

Check if it is possible to reach the exit of an outer switch from start_bid without going through the exit_candidate. We use the forward graph.

fn register_children_as_loop_exit_candidates( cfg: &CfgInfo, loop_exits: &mut HashMap<BlockId, IndexMap<BlockId, LoopExitCandidateInfo>>, removed_parent_loops: &Vec<(BlockId, usize)>, block_id: BlockId, )

Register a node and its children as exit candidates for a list of parent loops.

fn compute_loop_exit_candidates( cfg: &CfgInfo, explored: &mut HashSet<BlockId>, ordered_loops: &mut Vec<BlockId>, loop_exits: &mut HashMap<BlockId, IndexMap<BlockId, LoopExitCandidateInfo>>, parent_loops: Vec<(BlockId, usize)>, block_id: BlockId, )

Compute the loop exit candidates.

There may be several candidates with the same “optimality” (same number of occurrences, etc.), in which case we choose the first one which was registered (the order in which we explore the graph is deterministic): this is why we store the candidates in a linked hash map.

fn compute_loop_exits( ctx: &mut TransformCtx, body: &ExprBody, cfg: &CfgInfo, ) -> HashMap<BlockId, Option<BlockId>>

See [compute_loop_switch_exits] for explanations about what “exits” are.

The following function computes the loop exits. It acts as follows.

We keep track of a stack of the loops in which we entered. It is very easy to check when we enter a loop: loop entries are destinations of backward edges, which can be spotted with a simple graph exploration (see [build_cfg_partial_info_edges]. The criteria to consider whether we exit a loop is the following:

• we exit a loop if we go to a block from which we can’t reach the loop entry at all
• or if we can reach the loop entry, but must use a backward edge which goes to an outer loop

It is better explained on the following example:

'outer while i < max {
    'inner while j < max {
       j += 1;
    }
    // (i)
    i += 1;
}

If we enter the inner loop then go to (i) from the inner loop, we consider that we exited the outer loop because:

• we can reach the entry of the inner loop from (i) (by finishing then starting again an iteration of the outer loop)
• but doing this requires taking a backward edge which goes to the outer loop

Whenever we exit a loop, we save the block we went to as an exit candidate for this loop. Note that there may by many exit candidates. For instance, in the below 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...
...

Also note that it may happen that we go several times to the same exit (if we use breaks for instance): we record the number of times an exit candidate is used.

Once we listed all the exit candidates, we find the “best” one for every loop, starting with the outer loops. We start with outer loops because inner loops might use breaks to exit to the exit of outer loops: if we start with the inner loops, the exit which is “natural” for the outer loop might end up being used for one of the inner loops…

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: &CfgInfo) -> HashMap<BlockId, Option<BlockId>>

See [compute_loop_switch_exits] for explanations about what “exits” are.

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.

fn compute(ctx: &mut TransformCtx, body: &ExprBody, cfg_info: &CfgInfo) -> Self

Compute the exits for the loops and the switches (switch on integer and if … then … else …). We need to do this because control-flow in MIR is destructured: we have gotos everywhere.

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 loop, 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.).

Finally, some similar issues arise for loops. For instance, let’s consider the following piece of code:

while cond1 {
  e1;
  if cond2 {
    break;
  }
  e2;
}
e3;
return;

Note that in MIR, the loop gets desugared to an if … then … else …. From the MIR, We want to generate something like this:

loop {
  if cond1 {
    e1;
    if cond2 {
      break;
    }
    e2;
    continue;
  }
  else {
    break;
  }
};
e3;
return;

But if we don’t pay attention, we might end up with that, once again with duplications:

loop {
  if cond1 {
    e1;
    if cond2 {
      e3;
      return;
    }
    e2;
    continue;
  }
  else {
    e3;
    return;
  }
}

We thus have to notice that if the loop condition is false, we goto the same block as when following the goto introduced by the break inside the loop, and this block is dubbed the “loop exit”.

The following function thus computes the “exits” for loops and switches, which are basically the points where control-flow joins.

Trait Implementations

impl Clone for ExitsInfo

fn clone(&self) -> ExitsInfo

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ExitsInfo

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

Formats the value using the given formatter.