Expand description
How many values want a register at each point of a function, and how many registers there are to put them in.
Design: spec/optimizer/39-register-allocation.md section 39.7, and tamnd/rucc#1177.
This is the question the spill phase in crate::spill asks before anything is placed. A
point where more values are live than there are registers is a point where some of them have
to be in memory whatever the assignment does, and knowing that up front means the choice of
which ones can be made by what each costs, over the whole function, instead of by which value
the assignment happened to meet last.
§What is counted
A value is counted at every point crate::live says it is live at, in its own class. A value
an instruction can only read from memory is not counted, since it never wants a register. A
physical register an operand names is not counted either, because it is not a value the
allocator places.
The room at a point is every register the environment hands out in the class, less the ones an instruction takes outright there. A call is where that shows: at the point a call writes its results it destroys every register the convention says it destroys, and only the ones it saves are left for what lives across it.
§Why it may say less than the truth and never more
Both halves are counted so that the difference is a floor. A register a fixed operand claims for one value is still counted as room, though nothing else may be in it there, and the answer of a two address instruction is counted from where it is written rather than from where its source is read. Each of those makes the room look larger or the values look fewer than they are, so a point this says is over is really over, and it is over by at least as much as this says. The spill phase leans on that: taking no more values off a point than this says have to go is never taking off one that could have stayed for want of room there.
Structs§
- Pressure
- How many values want a register at each point, and how many registers there are for them.