Module assign 

Which register each value lives in, and which values live on the stack instead.

Design: spec/10-backend.md section 10.4.

This is the -O0 allocator’s decision and nothing else. It is linear scan over the line crate::order lays the function out in: the values are taken in the order they are written, each is given a register that nothing else live at the same time is in, and when there is no such register one of the values in flight goes to the stack instead. There is no splitting and no coalescing, so a value gets one place for the whole of its range and keeps it. That produces mediocre code quickly, which is what -O0 is for, and the allocator that produces good code slowly is a separate one, in M4.

Which value is sent to the stack is the one whose range ends last, counting the value being placed among the candidates. A value wanted for a long time is the cheapest to spill per instruction it frees a register over, and it is the only heuristic here. What is picked is really a register and not a value, since two values that are never both wanted share one, and then every value in that register which is in this one’s way goes.

Where the line is not the function

The line is the order the blocks arrived in, and crate::layout puts them in a different one afterwards, so being between two blocks on the line says nothing about being between them in the code. A value live in one loop and live again in a later one is written down with everything in between inside the interval around it, and it is not live in any of it.

Which is why what decides anything here is the area from crate::live, and the interval is only the sweep’s bookkeeping: it says which values to compare and the areas say which of them actually collide. Three loops one after another in a function put a dozen values in flight at the same instant of the line and never at the same instant of the program, and asking the interval would spill the one this loop is walking for the sake of eleven values in the other two. tamnd/rucc#982.

The same holds for a register an instruction insists on. A call destroys seven registers on x86-64, and a function whose blocks happen to arrive with a call written between the blocks of a loop would otherwise lose all seven for every value in that loop, for a call the loop never reaches, so that question is asked of the area and not of the interval either.

Allowed is not the same as free, though, so the registers are offered in two passes. First the ones nothing insists on anywhere the range reaches, then the ones something insists on somewhere the value never goes. The second kind costs: the instruction that insists has to be handed the register in the end, and what hands it over is a move. A function that gives a value back has an operand fixed to rax at the end of it, and putting the busiest value in the function in rax because no path reaches the return with it live buys one register and pays a move at every return. Ordering the two passes is what keeps the register and drops the moves.

The hint below is asked the first question rather than the second for the same reason. A value taking the register its own operand asked for saves a move, and taking one somebody else’s operand asked for somewhere it never goes costs one, so a hint is worth following when the register is clear and not worth following when it is merely allowed.

What it does with a register an instruction insists on

Two things. It stays out of that register for everybody else, and it tries that register first for the value the operand names. A division wants its dividend in rax, so rax is unavailable to every other value that is live where the division reads, and it is the first register offered to the dividend itself. When the dividend gets it there is no move on the way in, and when it does not the rewrite writes one and nothing else changes.

That second half is the hint, and without it the register an instruction insists on is the one register the value in it can never have, since the value’s own operand is what makes the register look busy. The effect is largest on returns, because a function that gives a value back has an operand fixed to rax at the end of it and most functions give a value back.

What makes the hint safe is asking about the register at each of the instruction’s two points rather than across the whole of it. An instruction reads at the first and writes at the second, so a register it insists on is one value’s at the first, another value’s at the second, and nobody else’s at either. A division reads its dividend from rax and writes its quotient to rax, and those are different values that can both live there. A value passed to a call in rdi and wanted again afterwards cannot, because nothing writes rdi at the second point and a register the call does not write is a register the call is assumed to destroy.

An operand that has to be in memory is the other way round. The value it names goes on the stack whatever else is true of it, because that is the only place the instruction could read it from.

What it does with a two address instruction

An add on x86-64 writes one of the registers it reads, which the operand says as a reuse of another operand. The rewrite can always make that true by copying the source into the destination first, but only if the destination is a register the instruction does not otherwise read, so a value written by a reuse is treated here as live from where the instruction reads rather than from where it writes. Then the copy is always safe.

The copy is also usually unnecessary, and the one place this looks past the interval it is placing is to see that: if the value being reused is read here for the last time and the value being written starts here, the second may have the first’s register, and the instruction is already two address without anything being moved anywhere. That is the whole of the coalescing this allocator does, and it is worth the dozen lines, because otherwise every piece of arithmetic in the output carries a move in front of it.

Both halves of that are needed. The second is the one a loop breaks: an instruction at the bottom of a loop can write a value the top of the loop reads on the next turn, and such a value is live on the way into the instruction that writes it as well as after. It is then wanted at the same time as the value it reuses, whatever is true of the reuse, and giving it the same register makes an addition read the answer to the last one instead of its own operand.

What it does not do

It does not touch the function. What comes out is a table saying where each value went, and the pass that rewrites the operands and writes the moves reads it. Keeping the decision and the rewrite apart is what lets the decision be checked by looking at it, and it is the shape spec/10-backend.md section 10.4 asks for: an allocator is a function from a program to an assignment and the moves that make it true.

Structs

Assignment

Where every value in a function went.

Env

What the allocator is allowed to use.

Enums

Place

Where a value lives.

Functions

assign

Decides where every value in a function lives.