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 it does with a register an instruction insists on

Nothing, except stay out of it. A division wants its dividend in rax, and the answer here is not to give the dividend rax for the whole of its life. It is to leave rax free at that one instruction, so that a move can put the value there on the way in. That costs a move the backtracking allocator will not need, and it buys one rule that holds everywhere: an operand with a fixed register is a fact about the instruction, not about the value in it, so it makes that register unavailable to everything across that instruction rather than claiming a value.

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, the value being written may have its 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.

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.