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
One interval per virtual register, with no holes in it. A value that is dead in the middle of its range is treated as live there, which costs a register the allocator could have handed out and never claims one is free when it is not. Holes are what the backtracking allocator will want and it will want a different structure to hold them in, since a range it can split is a range with a list of pieces rather than two numbers.
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 intervals then come from one walk over the instructions. A block a value is live through contributes the whole of that block, which is what makes the interval cover the loop rather than stopping at the last instruction that mentions it.