Expand description
Where each local the program kept in a value ended up, and over which instructions.
Design: spec/11-asm-objects-debug.md section 11.4.
Selection says which declaration each virtual register holds a value of, and the allocator says
where each virtual register went. Putting the two together is all this is, and the only thing
that makes it more than a join is the stretch: a frame slot belongs to its local for as long as
the frame exists, and a register is handed to the next value the moment this one is done with,
so where a register holds a local is a question about part of a function rather than about the
whole of it. The allocator’s own liveness is the answer, read rather than worked out again for
the reason crate::slots gives for reading it: two answers about one function are free to
disagree, and the one the machine runs is the allocator’s.
A stretch runs from the instruction after the one that wrote the value to the last instruction that reads it, both ends included, and it stops at the end of the block either way. The front is one instruction along because a register does not hold a value until the instruction writing it has run, and the back is where it is because nothing reads the value afterwards, so whatever the allocator puts in the register next cannot be seen by anybody asking. A value nothing reads at all gets no stretch, which is the same sentence read the other way: the two ends cross.
The block is where it stops because the pass that lays the blocks out runs after the allocator and can put them in any order it likes. Inside a block nothing has moved, so a run of instructions there is a run of addresses to come, and a value live from one block into the next gets a stretch in each of them rather than one stretch that would cover whatever the layout happened to put in between.
§A block the scheduler reordered
The liveness is counted along the order the allocator laid the function out in, and the scheduler runs after it and moves instructions about inside a block, so in a block it touched a run of points is no longer a run of instructions. What is still true there is what the scheduler has to keep true for the program to mean the same thing: it runs after the registers are handed out, so every write of a register stays in order with every read of it and every other write of it, and every access to memory stays in the order it was in. So a value is in its register from the instruction after the one that wrote it to the last one that reads it, wherever the schedule put those two, and a local in the frame is in its bytes from the first touch of them to the last. A stretch in such a block is found by where its two ends went rather than by a search along the points.
That needs both ends to be an instruction the liveness knows, or the edge of the block for a value live into it or out of it. A piece that starts or ends at a spill, a reload or an edge move has an end that is neither, and it gets no stretch in that block rather than a guess.
§A declaration that took a value part of the way through
int m = a; computes nothing, so m is handed a value a already holds, and the value’s live
range says nothing about where the assignment was. Selection says it instead, as the first
instruction after it in Func::starts. In that instruction’s block the stretch starts no
earlier than it, and in any other block the declaration holds the value only where every path
from the entry goes through the assignment’s block first, which is where it is sure to have
run. A block the other arm of a branch reaches as well is left out, since there the
declaration may never have been given the value at all.
§A declaration with two values live into a block
A local written in a loop is the value from the last trip until the new one is computed, and
the old one can still be read after that, so both are live into the blocks between the write and
the back edge. Their stretches there start at the same address and say different things. Which
one the local is follows from the order the assignments ran in, and Func::entries is that
answer, worked out from the program before selection. A piece that comes into a block the entry
names another register for gets no stretch there. A piece that starts inside the block starts at
an assignment, and is kept either way.
§What is left out
A value the allocator spilled is in the frame over its stretch rather than in a register, which
is as much an answer as the other and is written the same way. A value it spilled in a function
whose alignment the prologue had to force has no answer, because the distance from the call
frame address is not a constant there, which is what crate::frame says about a local in the
same function.