[nll] avoid liveness for values that escape into the output when in a static

[nikomatsakis]

As an optimization for large statics like the ones in html5ever and so forth: we tend to spend a ton of time in liveness and elsewhere in these cases, but it seems a bit silly since we know that any references or lifetimes which flow into the result must be 'static.

The idea would be something like this:

• Before computing liveness, we do a pass over the MIR.
• We create a union-find set of Local values.
• Whenever we see a statement like _0 = _1 or _0 = Aggregate { _1 } or _0 = &_1, we union together _0 and _1 -- basically, the idea is we union _0 and _1 whenever the type of _0 must contain any of the lifetimes in _1.
• Then at the end we check which things are union'd with _0 -- for those variables, we do not have to compute liveness, and can instead just force all of their regions to outlive 'static.

I .. think that's sound =)

Example:

#![feature(nll)]

pub struct Map<K: 'static, V: 'static> {
    pub key: u64,
    pub disps: Slice<(u32, u32)>,
    pub entries: Slice<(K, V)>,
}

pub enum Slice<T: 'static> {
    Static(&'static [T]),
}

pub static NAMED_ENTITIES: Map<&'static str, (u32, u32)> = Map {
    key: 1897749892740154578,
    disps: Slice::Static(&[
        (1, 4),
        (1, 4),
        (1, 4),
        (1, 4),
        (1, 4),
        (1, 4),
        (1, 4),
    ]),
    entries: Slice::Static(&[
        ("GreaterSlan", (0, 0)),
        ("GreaterSlan", (0, 0)),
        ("GreaterSlan", (0, 0)),
        ("GreaterSlan", (0, 0)),
        ("GreaterSlan", (0, 0)),
        ("GreaterSlan", (0, 0)),
        ("GreaterSlan", (0, 0)),
    ]),
};

fn main() {
}

[lqd]

I might not be able to finish before going on vacation, but I'm looking at this, and will update the Zulip topic with any progress, in case someone wants to pick this up if need be.

[nikomatsakis]

Just realized that while the underlying idea here is sound, the means of implementation is totally flawed. The problem is using union-find, which establishes a bidirectional link. This program for example type-checks now, but should not:

#![feature(nll)]

fn foo<'a>(x: &'a mut u32) -> u32 {
    let mut x = 22;
    let y = &x;
    if false {
        return x;
    }

    x += 1;
    println!("{}", y);
    return 0;
}

fn main() { }

[nikomatsakis]

OK so I opened #53109 to revert my incorrect changes.

[nikomatsakis]

I think that the correct fix is to replace the code that uses union-find with a directed graph. Basically we add an edge A -> B if the entire type of A will be incorporated into B's type. Then we walk backwards from the return place _0 to find all variables.

In terms of broken example I cited, what is happening is that we have:

x -> y
x -> ReturnPlace

Using union-find means that x, y, and ReturnPlace are all grouped together (essentially, we have an undirected graph). But if we use a directed graph we would just consider x as escaping (correctly) and not y.

[nikomatsakis]

Another thought: I think that we can rejigger things so that — by the time we compute liveness — we have the outlives relations at hand. That would in some sense be "ideal" -- we would skip computing liveness precisely when we care, rather than the current code which duplicates some of the logic.

On the other hand, analyzing the outlives relationships is a bit more complicated, since we have to look at all the regions in a variable's type.

I guess the would be something like this:

• We compute the set of regions that are required to outlive free regions (any free region will do).
• Then we iterate over the regions in a variable's type -- if all of them are required to outlive free regions, we skip computing liveness for it.

Hmm, sounds not that complex, actually -- the main work will be refactoring to push the liveness computation down so that it occurs later (in particular, constructing the liveness map later). Now that I think about it, it is ok if we still add more outlives constraints after computing liveness (which I think we may do in some cases owing to normalization), because adding more constraints would only cause us to skip MORE liveness.

[nikomatsakis]

I was trying to write up mentoring instructions for this but felt like it'd be easier to just implement the dang thing. Hence #53168

[lqd]

This was completed in #53177

[nikomatsakis]

Yes, it was. =)