Expand description
The allocation checker: whether an assignment is one the machine can actually run.
Design: spec/10-backend.md section 10.4, which asks for this in debug and CI builds.
A register allocator is the pass whose bugs are hardest to find from the outside. It does not change what a program means, so a wrong allocation compiles, links and runs, and then produces the wrong number in one function of one program under one register pressure. The stack trace points at the arithmetic, the arithmetic is right, and the value it read was overwritten four instructions earlier by something unrelated. A checker turns all of that into an assertion at the point the mistake was made, naming the two values and the register they were both put in.
§What it asks
Four questions, and they are the whole of what an assignment has to get right.
Every value the function uses has somewhere to live. Two values that are both wanted at the same point are not in the same register or the same slot. Nothing is sitting in a register that an instruction insists on for itself, because that register belongs to the instruction for as long as it runs. A value an instruction can only read from memory is in memory.
§What it does not ask
Whether the allocation is any good. A function with every value on the stack passes, and so it
should: it is slow and it is correct, and this is the thing that says which of the two a
problem is. Quality is what the numbers in spec/14-target-ladder.md are for.
It also does not read the rewrite. It runs on the assignment, before crate::rewrite has
touched the function, because the assignment is the decision and the rewrite is a
transcription of it. A rewrite that transcribes a good decision badly is a different bug and
the tests in that file are what catch it.
§Why it repeats work
The two address instructions are worked out again here rather than borrowed from
crate::assign, and that is deliberate. A checker that shares its reasoning with the thing
it checks agrees with it about everything, including the mistakes, and the one bug it can never
find is the one in the code they share. Fifteen lines is a cheap price for a second opinion.
It is also allowed to be slow. Looking for a value in a register an instruction wants is the plain product of the values and the constrained operands, with no index over either, because a checker runs in debug builds and in CI and the thing it is checking is the thing that has to be fast.
Enums§
- Problem
- One thing wrong with an allocation.