Expand description
Putting a set of moves that happen at once into an order they can happen in one at a time.
Design: spec/10-backend.md section 10.4.
The parameters of a block arrive from every edge into it, and after allocation each of them is a place and each argument is a place, so an edge becomes a set of moves. They all happen at once: every argument is read as it was at the end of the predecessor, and nothing an edge writes is visible to anything else the edge writes. A machine does not have that instruction. It has one move, and the moves have to go in an order.
Most of the time any order will do, but not always. Two parameters that swap two values are
two moves that each destroy what the other wants to read, and no order of the two is right.
The way out is a third place to keep one of the values in, which is the scratch, and the
algorithm below is the one that finds out when one is needed and writes as few extra moves as
it can. spec/10-backend.md says this is a small algorithm that is wrong in a startling number
of compilers, which is why it is written here on its own and tested on its own rather than
being a loop inside the allocator.
Nothing here knows what a place is. A place is a register after allocation, or a stack slot for a value that was spilled, and the algorithm is the same either way, so the caller says what its places are and gets the same kind of thing back.
Structs§
- Move
- One move: what is written, and what is read.
Functions§
- sequence
- The moves in an order they can be made in, one at a time.