MIR: permit "false edges", that are only used in the analysis

[nikomatsakis]

As discussed in #45043, we sometimes want to have false edges in the MIR that are used by borrowck and other conservative safety analyses, but which are optimized away when we actually generate code. The current hack is to e.g. replace a GOTO X terminator with something like IF TRUE { X } ELSE { Y }. This works (and should be optimized away), but it's not that flexible, and not that obvious.

It'd be nice to have something more first class. This could look like a vector of false_edges: Vec<BasicBlock> as part of BasicBlockData (that would get cleared after analysis), but that's a bit unfortunate since in that case they can be easily overlooked, since the code now has to remember to look not only at the terminator but also elsewhere.

On Gitter, we were thinking that a nice approach might be to add a new TerminatorKind variant named something like FalseEdges. This could even wrap the "true" terminator and then add additional edges:

enum TerminatorKind {
    ...
    FalseEdges(Box<FalseEdgesData>) // introducing box here keeps total size down
}

struct FalseEdgesData {
    true_terminator: TerminatorKind,
    false_edges: Vec<BasicBlock>
}

This would then be replaced with the true_terminator by the terminator simplification code.

For now, places that could benefit from this are marked with FIXME.

The steps to make this change are roughly:

• Introduce the variant listed above. Get things to compile. Reach out to myself or others on gitter if weird things arise in the process.
• Modify the terminator simplification code to replace FalseEdges with the underlying true terminator.
• Replace the existing code using hacky false edges with the new stuff.
• Huzzah!

[nikomatsakis]

cc @pnkfelix @mikhail-m1 @arielb1

[arielb1]

@nikomatsakis

I think a terminator wrapper would just be annoying for all analysis passes in the middle that would forget to unwrap it. I would rather have a

enum TerminatorKind {
// ...
    FalseEdges {
        real_target: BasicBlock,
        imaginary_targets: Vec<BasicBlock>
    }
}

[nikomatsakis]

I think a terminator wrapper would just be annoying for all analysis passes in the middle that would forget to unwrap it. I would rather have a

I'm fine with that; the only reason to have a wrapper that I can see is if we wanted to add false edges to something more complex than a GOTO. That said, I'm not sure what you mean by forget to unwrap it -- if they are doing a match, they must handle the case, and if not, they are probably using the successors() function which would presumably do the right thing, right?

[arielb1]

That said, I'm not sure what you mean by forget to unwrap it -- if they are doing a match, they must handle the case

I mean, a pass could look for e.g. TerminatorKind::Call using a non-exhaustive match (or an if-let), but miss a call that is embedded within a TerminatorKind::FalseEdges.

[nikomatsakis]

@arielb1 I see, that's true. All the more reason to avoid non-exhaustive matches =)

I guess in the end it depends on whether we ever want to add false edges to anything but a plain goto. I suppose we could introduce dummy basic blocks too.

Do you remember where we wanted false edges for match lowering? I think the idea was to safeguard ourselves with respect to when arm guards would execute in some respects.

[arielb1]

@nikomatsakis

IIRC the idea was to add a false edge from both the start and the "false" end of each "possible" guard to the start of the next one, so e.g.

match x {
    Some(w) if guard() => ...,
    x => ...,
    Some(y) if guard2(y) => ...
    z => ...
}

becomes

// the first match arm should always be reachable, so I
// don't think this one is really needed
if false { goto before_guard_0; }
match x {
    unreachable:
        unreachable
    Some(w) =>
before_guard_0:
        if false { goto before_guard_1; }
        if guard() {
            ...
        } else {
            if true { goto next; } else { goto before_guard_1; }
        },
    x =>
before_guard_1:
        // yes, this fake edge can bind `y` when the current variant is
        // `None`, but this shouldn't break anything because the edge
        // is never actually taken.
        if false { goto before_guard_2; }
        ...
    Some(y) =>
before_guard_2:
        if false { goto before_guard_3; }
        if guard2(y) {
            ...
            break;
        } else {
            if true { goto next; } else { goto before_guard_3; }
        },
    z =>
before_guard_3:
        // just here for completeness - shouldn't have any effect
        if false { goto unreachable; }
        ...
}

[arielb1]

The reason we want both edges is because we don't want to "trust" the actual internal match edges - we want to be able to do whatever we want there, so we must have a more general set of edges. The match flow can both skip a guard (because the pattern wouldn't match) and go from a failed guard to the next arm (instead of skipping over a few arms in the internal match code because we "keep track" of failed matches).

[arielb1]

Note: the main reason you want the big exoskeleton is because we want a future-proof solution to #29723 - you can observe reachability by moving a variable in one match guard and accessing it in another guard/arm, or after we get a sane mutability/guards situation by reinitiallizing a variable in one match guard and accessing it in another.

[circuitfox]

I'd like to work on this if no one else is already.

[mikhail-m1]

actually I've already started, but may be we can split it, let's discuss on gitter

[arielb1]

```Rust
match x {
    Some(w) if guard() => ...,
    x => ...,
    Some(y) if guard2(y) => ...
    z => ...
}

becomes

// the first match arm should always be reachable, so I
// don't think this one is really needed
if false { goto before_guard_0; }
match x {
    unreachable:
        unreachable
    Some(w) =>
before_guard_0:
        if false { goto before_guard_1; }
guard_start_0:
        if guard() {
            ...
        } else {
guard_fail_0:
            if true { goto next_0; } else { goto before_guard_1; }
        },
    x =>
before_guard_1:
        // yes, this fake edge can bind `y` when the current variant is
        // `None`, but this shouldn't break anything because the edge
        // is never actually taken.
        if false { goto before_guard_2; }
guard_start_1:
        ...
    Some(y) =>
before_guard_2:
        if false { goto before_guard_3; }
guard_start_2:
        if guard2(y) {
            ...
            break;
        } else {
guard_fail_2:
            if true { goto next_2; } else { goto before_guard_3; }
        },
    z =>
before_guard_3:
        // just here for completeness - shouldn't have any effect
        if false { goto unreachable; }
guard_start_3:
        ...
}

[arielb1]

I think this can be closed, given that the false edges have been implemented.