Expand description
Which values are live where, which is what the pressure model counts and what a scheduler has to know before it moves anything.
Design: section 40.6 of spec/optimizer/40-cost-models.md, which needs this before it can
count anything, and document 39.5, which is where the count becomes meaningful.
§Live means used later, and in this IR that is exact
A value is live at a point when some path from that point reaches a use of it. The IR is in SSA with block parameters rather than phi nodes, so the awkward case other compilers have here does not arise: a phi’s operand is used in the predecessor and not in the block holding the phi, which every liveness implementation over phi nodes has to special case and half of them get wrong. Here the argument travels on the branch, the branch is an instruction in the predecessor, and the ordinary rule that an instruction uses its operands already says the right thing.
§The fixpoint
Backwards, over the reverse of reverse postorder, until nothing changes. A block’s live-in is what is live at its first instruction with its own parameters taken out, since a parameter is defined by arriving. Its live-out is the union of the live-ins of its successors. Postorder means a block is visited after the blocks it branches to wherever the graph allows, so the usual function settles in one round and a loop costs one more.
A value passed as a branch argument is live at the branch and not on the edge, because what
crosses the edge is the parameter it becomes. Liveness::through is where a caller sees it,
and it is the walk the pressure model counts along, so the argument is counted where it is
actually held.
§What is not counted
Values of type mem are the memory dependence chain and are not data. They are live in the
same sense as anything else and Liveness reports them, because a pass asking whether a
store is still needed wants them. The pressure model is what drops them, because memory is not
held in a register, and that decision belongs where the registers are being counted rather than
here.