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

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, 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.