[NLL] integrate liveness with inference

[nikomatsakis]

Once #44904 is fixed, the next step is to start adding constraints. I think that the liveness constraints are the easiest to add. These come in two forms. The first part are the constraints that are due to active uses, and the other are constraints due to drops.

The basic idea is this:

• If at some point P a value V may be used again (excluding future drops):
  • Then all lifetimes appearing in the type of V must be live at P.
• If at some point P a value V may be dropped:
  • Then all lifetimes appearing in the type of V which are not marked as may-dangle must be live at P.

That said, I think that, for this first issue, we should basically just ignore the special case of drop. In fact, we are going to want to make a few further refinements as discussed here -- in particular extending this code to consider not only liveness, but also which values are initialized. Let's ignore all of that for now and just get the basics up and going.

As it happens, we have some existing code for computing which values are live, located here. Unfortunately, it has some limitations:

• First off, it doesn't distinguish drops from other uses, but let's ignore that for now.
  • In the prototype, distinguishing drops is done by having two distinct bits that we track per variable.
• Second, it only computes the liveness at basic block boundaries.
  • We're going to need finer-grained information.
  • The liveness code has the kind of "classic" setup of computing overall defs and uses for the entire basic block, then applying those.
  • In the prototype, we use a slightly different setup, where we
    1. have one big bit-set storing all the things that are live on entry to a basic block -- we don't store the things live on exit, we can easily recompute that by unioning together the preds
    2. have a function walk() that will tell you what is leave in between each action in a basic block:
       • it starts by taking the union of all things live in successors of the block
       • invokes the callback to indicate the things live before the terminator starts
       • then it walks each action:
         • adjusts the set of things live to account for the action's effects
         • and invokes a callback with the intermediate result
       • then take the final result to update the set of things live on entry, if it changed

I'm not sure if we want to take precisely the same approach with the liveness code or not. It's a convenient setup, in any case, since we can then re-use this same "simulate" code to compute the fixed-point and -- after the fixed-point is computed -- to find the live bits at any particular point within the basic block.

Anyway, I have to run now, so I'll try to write up more mentoring notes later on.

[spastorino]

Already talk to Niko about this, I'll be working on this one.

[nikomatsakis]

OK, so, ultimately I see two options here. Either we use the "simulate" approach I described above, where we store the live things on block entry, and then have some function that will walk the actions of a block (in reverse order), applying their effects to a starting bit set, or else we ignore basic blocks and just store the "live on entry" set for every location in the CFG.

The advantages of the simulate approach is primarily that you don't store nearly as much data (one bit set per block vs per location -- big difference!). The disadvantage is that, during the "iterate until fixed point" phase, you are paying some cost by resimulating the effects of each action in the block. The current code uses the more classical operation, computing the total effect of each block in a single pass, and then in the fixed point iteration re-using that information.

Storing a bit set per each location is actually not a good design. It's kind of worst of all worlds: large memory requirements and its slow. Unlike today's code, which "sums up" the effects of a basic block into two delta bit sets (defs, kills) and then applies those in one fell swoop, storing a bit set per location would still involve iterating over each location. Silly idea.

However, there is a hybrid approach. You define a "simulate" function but it does not apply its effects directly to a bit set, but rather computes "deltas". You can then accumulate these deltas to block granularity for reaching a fixed point, but also replay them at finer granularities for computing the intra-block values.

That said, my current take is that we should just do the original "simulate" approach I described. It's mildly simpler to apply effects directly to a real bit set versus describing them in terms of gens/kills, and I don't think that it will take so many iterations to reach a fixed point (nor that the cost of "interpreting" each action will be so expensive). We can always refactor later.

Actually, I'm vaguely changing my mind. I think I don't care too much but at minimum we can probably factor the "simulate" function into one that returns a set of gen/kill bits.

[Nashenas88]

So if I've read this correctly, the hybrid approach you're suggesting is one that produces a set of gen/kill bits where each unit of gen/kill bits corresponds to one point in the basic block, right? This would allow us to do something like the following

• Given I have a value I want to compute the lifetime for, I can walk a basic block that already has a set of gen/kill bits generated
• At each point of the basic block if there is a gen or kill bit that applies to this value, I modify the lifetime appropriately
• Once I've walked the entire block, I have the complete lifetime for that value while it's in that block
• Doing this for all basic blocks within a Mir block would allow us to compute the lifetime of the value in the function-like block

The above is just an example of what we might be able to code, not something we want to code exactly like that. Do you see anything wrong with my interpretation here?

[nikomatsakis]

@Nashenas88

I'm not sure I quite followed your example, but:

one that produces a set of gen/kill bits where each unit of gen/kill bits corresponds to one point in the basic block

Right, so I was saying that you can imagine that for any Location we can produce a set of gen/kill bits for the statement at that location (for locations that correspond to terminators, the sets would be empty). We might precompute these and store in a hashmap, or we might just compute them on the fly, since they are probably quite cheap to produce. Let's just for now say there is a function GEN(L) that -- for any location L -- returns the gen bits, and KILL(L) that returns the kill bits.

This is similar but slightly different from the prototype: there, I have this function Action::def_use that indicates which variables are "defined" (roughly: kill bits) and "used" (roughly: gen bits) by a given action. The difference is that the prototype is returning sets of variables, but really variables have multiple bits (e.g., the bit corresponding to "drop" vs the bit corresponding to "regular use"). This requires some adjustments later that handle the drop bits (I think this "skolemized end" stuff is basically dead code, btw and can be ignored.)

Anyway, given gen(L) and kill(L), we can devise various impl strategies. The prototype basically iterates to fixed point by doing:

let mut live_on_entry: Map<Block, BitSet> = ...;

while not yet at fixed point {
    for each block B {
        let mut bits = union of live_on_entry(S) for each successor S of the block B;
        for each location L in B (going backwards) {
            bits = bits - kill(L) + gen(L);
        }
        live_on_entry(B) = bits;
    }
}

But the key point is that one could optimize that inner for loop by pre-computing gen(B) and kill(B)-- basically, the gens and kills across the whole basic block. This is what the code is doing today. This makes sense since we are not really interested in the intermediate values ofbits` that we obtain as we traverse the individual locations.

However, we do still want to have ready access to kill(L) and gen(L) -- i.e., for a single location -- because the inference code is going to need to compute those intermediate values later on, since they are needed for liveness.

The above is just an example of what we might be able to code, not something we want to code exactly like that. Do you see anything wrong with my interpretation here?

I think what you wrote seems correct. It's just a touch confusing because I don't think we would ever be trying to compute the liveness for a "single value" the way you described. i.e., we'd probably rather iterate over all the points and compute the values that are live at each point, rather than iterating over the values, and computing the points where that value is live (the latter seemed to be more what you are describing). But in principle you could do either.

(Actually, I guess you could do it either way, but computing all values live at a particular point is the more standard way to express it.)

[nikomatsakis]

This is long since done.