Expand description
The linear order the allocator works over, and the positions in it.
Design: spec/10-backend.md section 10.4.
A live range is an interval, and an interval needs the program laid out in a line. The line
is the function’s own block order, because spec/10-backend.md section 10.3 says the -O0
path does no block layout beyond preserving the order it was given, and because that is the
order the encoder will write the blocks out in. An allocator that worked over some other
order would be allocating for a program nobody emits.
§Where the points are
Every instruction has two of them. An operand is read at the first and written at the second, which is what makes a two address instruction possible at all: the register a value is read from is free by the time the result is written, so the two can be the same register, and an operand written early is written at the first point instead, where it collides with every operand read there. That is the whole meaning of an early definition and it is the reason the points come in pairs rather than one to an instruction.
Every block has two more. The parameters arrive at the point in front of its first instruction, and the arguments its terminator carries away are read at the point after its last, which is where the moves that write the successor’s parameters will go. Neither is an instruction, and both are places where something is live.
Structs§
- Order
- The blocks in the order they are emitted in, and the point every part of them is at.
Type Aliases§
- Point
- A place in the function, counted along the line the blocks make.