Module backtrack 

Which register each value lives in, decided in the order the values are hardest to place, and undone when a value that would cost more to lose finds its register taken.

Design: spec/optimizer/39-register-allocation.md section 39.7, and tamnd/rucc#1177.

crate::assign is the -O0 answer. It walks the line once, and when it runs out of registers the value that goes to the stack is the one whose range ends last. That is a guess about cost made from a fact about length, and it is wrong exactly where it matters: a value read in every turn of a loop and wanted again after the loop ends last, so it is the one that goes, and every turn of the loop pays a load for it.

This answers the same question with the cost in it. Every value gets a weight, which is how often it is read or written, each time counted by how often the block it happens in runs, over how much of the function it is live across. A value with a high weight is one that would cost a lot to keep in memory for little register in return, and that is the one to keep.

The order values are placed in

Longest first. A long value meets more of the others than a short one does, so it has the fewest registers to choose from, and giving it first choice is what leaves the short ones something to fit into. That is the order LLVM’s greedy allocator takes them in, for the same reason.

Backtracking

Going longest first means a long cold value takes a register before a short hot one has been looked at. When the hot one comes and finds nothing free, it asks what it would cost to take a register back. For each register the answer is the values in it that are in the way, and the register can be taken when every one of them weighs less than the value asking. Of the registers that can, the one taken is the one whose heaviest value in the way is lightest. The values that lose it go back in the queue and look for another register, and a value that has lost one ROUNDS times goes to the stack instead of looking again.

That rule is also why it stops. A value only ever takes a register from values lighter than itself, and each value is put back a bounded number of times.

What it keeps from the linear scan

Everything that says what a register may hold. The registers an instruction insists on, the values an instruction can only read from memory, the two address instructions and the hints are all read the way crate::assign reads them, from the same functions, so the two allocators cannot disagree about what the machine allows. They only disagree about who gets the register, and crate::check asks the same questions of either answer.

A two address instruction is coalesced from both ends here. The linear scan only ever meets the answer after its source, since the source is written first. Here either can be placed first, so a source looks at where the answer that reuses it went as well as the other way round.

When it gives up

Every question of whether two values are both wanted is counted, and a function that asks more than BUDGET of them is handed to the linear scan instead. The answer is worse and it comes out in time, which is what the section asks of a pathological function. It is a count of work rather than of values because a function with many short values that never meet is cheap however many there are.

What the spill phase adds

It runs twice when crate::pressure finds a point with more values live than registers. Once as above, where a value goes to the stack only when the queue reaches it and it can take no register back, and once with the values crate::spill picked sent to the stack before the queue starts. The first is better where the pressure is brief and eviction settles it in a few moves. The second is better where it is long, since the values that go are picked by weight across every point that is over rather than by which one the queue met last. Neither wins everywhere, so both are costed.

It also gives up when it would lose. The linear scan runs as well, which is cheap next to this, and the answer kept is the one with the lower cost: the loads and stores of the values on the stack and the copies between the ends of each tie left apart, each counted by how often its block runs. Placing the long values first is right where registers are fought over in a loop, and it can be worse in a long straight run of arithmetic, where the order the linear scan walks in is also the order that lets each answer follow its source.

Constants

BUDGET

How many questions of whether two values are both wanted a function may ask before it is handed to the linear scan.

ROUNDS

How many times a value may lose its register and look for another before it goes to the stack.

Functions

assign

Where every value goes, in the order that places the hard ones first and takes a register back when a heavier value wants it.

cost

What an assignment is expected to cost a function, in instructions each counted by how often its block runs.

within

The same, with the budget said, or None for a function that went over it.