Expand description
Where every value in a machine function is live.
Design: spec/10-backend.md section 10.4.
A register can be given to two values at once exactly when the two are never both wanted, so this is the question every allocator asks first and the one both of ours will read the answer to from here. It is asked of the machine IR while it is still in SSA form, which is what makes the answer cheap: a value is written once, so its live range is one interval from where it is written to the last place it is read, and there is no need to ask which of several definitions a use is reading from.
§What the answer is
A list of pieces per virtual register, one for each run of blocks the value is live over, and the interval around them for anyone who only wants to know where a value starts and stops.
The pieces are what it takes to say that a value live in one loop and live again in a later one is not live in between. Both loops are in the same line of points, so an interval that covered them both would cover everything laid out between them and every value in there would look like it was competing for a register with one it never meets. Twelve such values in a row are twelve registers gone on a machine that has twelve, which is how a function using half the machine ended up spilling. tamnd/rucc#982.
Being dead in a piece’s hole means dead for good rather than dead for a while. A value is live in a block when a use of it can still be reached from there, so a block it is not live in is one that no execution reaching it ever reads the value again. That is what makes a hole safe to hand to somebody else without splitting anything: whoever gets the register in there is not borrowing it, and nothing has to be put back afterwards.
Physical registers in the operands are not in the answer. Nothing writes one before allocation except an instruction that must, and what a call destroys is a separate question that the ABI lowering asks, so a pass that reads this is reading about the values the allocator places.
§How it is computed
Which values arrive live in each block and which leave live is a fixpoint over the blocks, run backwards because liveness flows backwards, and it is a fixpoint rather than one pass because a loop carries a value from the end of a block round to a block in front of it. The pieces then come from one walk over the instructions, a block at a time.
Inside one block a value’s live points are one stretch and never two, because the machine IR is in SSA form and a value is written once. The stretch runs from the start of the block if the value arrives live and from where it is written otherwise, and to the end of the block if it leaves live and to its last read otherwise. Two stretches join into one piece when the blocks they are in are next to each other in the line, which is what makes a value carried round a loop one piece over the whole loop rather than one per block in it.