Expand description
Both register allocators and the allocation checker.
Design: spec/10-backend.md. Layer rank 11, see spec/18-package-layout.md.
§Status
Liveness is here, which is the question both allocators ask first: order lays a function
out in the line the encoder will emit it in, and live says where in that line each value
is wanted. So is moves, which puts the moves an edge turns into in an order they can be
made in one at a time. The single pass allocator’s decision is in assign: where every value
of a function goes, in one linear scan, which is what -O0 asks for. The rewrite that makes
that decision true in the function is in rewrite, and run is the two of them together,
which is the whole of the -O0 allocator. check reads an assignment back and says whether
it is one the machine can run, which run asserts on in debug and CI builds and which the
backtracking allocator is held to the same way. trace asks the other half of the question,
which is whether the rewrite wrote that decision down without losing a value on the way: it
follows every value from the instruction that wrote it to the instructions that read it,
through the moves, and run asserts on it in the same builds.
The allocator the optimizer uses is in backtrack. pressure counts, at every point, the
values that want a register against the registers there are, and spill reads that to pick
which values go to memory before backtrack places the rest.
Every crate in the workspace is published, and publishing implies a promise. This one is
tier 3: its Rust API is explicitly unstable and will change without a major version bump.
Depend on the rucc binary’s behaviour, not on this.
Modules§
- assign
- Which register each value lives in, and which values live on the stack instead.
- 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.
- check
- The allocation checker: whether an assignment is one the machine can actually run.
- live
- Where every value in a machine function is live.
- moves
- Putting a set of moves that happen at once into an order they can happen in one at a time.
- order
- The linear order the allocator works over, and the positions in it.
- pressure
- How many values want a register at each point of a function, and how many registers there are to put them in.
- rewrite
- Making an assignment true in the function it was worked out for.
- spill
- Which values go to memory before any register is handed out.
- trace
- Following every value from the instruction that wrote it to the instructions that read it.
Structs§
- Allocation
- What allocating a function produced.
Enums§
- Allocator
- Which of the two allocators decides where the values go.
Constants§
- MILESTONE
- The milestone in
spec/17-milestones.mdthat fills this crate in.