Selection gave you a sequence of machine operations. Now every value needs a register, and there are far more values than registers. That part is arithmetic. The hard part is that a register is a name with a lifetime — two values whose live ranges overlap cannot share a register, two whose ranges do not overlap can, and deciding which pairs overlap is the entire subject.
There are three classic answers, all written here, all run on the same IR:
$ python3 compback.py --run | sed -n '/ linear scan Braun/,/QUOTED A REPRODUCIBLE NUMBER/p'
linear scan Braun & Hack, CACM 21(10) 1978. Sorts intervals by
start point and needs NO interference graph -- only
the intervals, which can be built in one pass.
Chaitin colour Chaitin/Briggs/Panter/Scholz 1979. Simplify, select,
spill, on a graph whose nodes are virtual registers
and whose edges are interference.
colour, iterate Greedy colour first, spill what will not colour,
repeat. §KEEP§THE THIRD IS NOT IN THE TEXTBOOK AND
IT EXISTS HERE BECAUSE THE THREE SPILL COUNTS
DISAGREE, AND A COMPARISON THAT QUOTES ONE NUMBER
WITHOUT SAYING WHICH POLICY PRODUCED IT HAS NOT
QUOTED A REPRODUCIBLE NUMBER AT ALL.
Linear scan needs no interference graph at all — it sorts intervals by start point and never builds the graph, so the graph’s size never matters. That is a fact about complexity rather than about quality, and the page comes back to it, because it is the reason production backends use the algorithm that looks worse here.
MEASURED-ON-BYTES. Nothing in the three tables below was timed and nothing was executed. A register allocation is a naming, and a naming is checked by running the lowered program and reading each value back out of its physical location. The three per-kernel tables are those runs. The one timing section on this page is section 10 of the artifact and it is labelled separately, and it is the only place in this course where a machine runs anything.
$ python3 compback.py --run | sed -n '/^ linear scan 58 spills/,/QUOTED A REPRODUCIBLE NUMBER/p'
linear scan 58 spills across 36 allocations
Chaitin colour 166 spills
colour, iterate 45 spills
the ratio Chaitin/linear is 2.86, and §KEEP§IT IS NOT A CLAIM
ABOUT THE ALGORITHMS. §KEEP§IT IS A CLAIM ABOUT THE SPILL HEURISTIC,
AND THE SAME GRAPH WITH A THIRD POLICY GIVES A THIRD NUMBER. §KEEP§THE
HONEST SUMMARY IS: WHICH ALLOCATOR IS BETTER IS A PROPERTY OF YOUR
CORPUS, AND A BACKEND THAT REPORTS "GRAPH COLOURING SPILLS N"
WITHOUT NAMING THE POLICY HAS REPORTED NOTHING REPRODUCIBLE.
58, 166 and 45. The same IR, the same interference graph, three spill policies. The ratio between the first two is 2.86, and the sentence that matters is the one after it:
That is why the third allocator is here even though it is not in the textbook. A comparison that quotes one number without saying which policy produced it has not quoted a reproducible number at all — and a three-way comparison is the only way to demonstrate that inside one page, because with two allocators a reader cannot tell whether the difference is the algorithm or the heuristic.
Each kernel’s table ends in a column that says yes nine times, and that word means something specific:
$ python3 compback.py --run | sed -n '/every "yes" is a CHECKSUM/,/WAS THE THIRD BUG THIS FILE/p' | head -9
every "yes" is a CHECKSUM, not a count: the program was
lowered with the spills, run by cbir.step, and every virtual
register's value read back out of its physical location at its
last use. §KEEP§THE READ-BACK IS AT THE LAST USE AND NOT AT
THE END OF THE PROGRAM, BECAUSE A SPILL SLOT MAY LEGITIMATELY
BE REUSED. §KEEP§READING IT AT THE END REPORTS AN ERROR IN A
CORRECT ALLOCATION, AND THAT WAS THE THIRD BUG THIS FILE
SHIPPED.
The read-back is at the last use, not at the end of the program, because a spill slot may legitimately be reused by a later value. Reading at the end reports an error in a perfectly correct allocation — and that was a real bug this artifact shipped, found because the column said no and the count said the allocation was fine.
So: nine yes means every spilled value still held the right number in the right place when it was last needed. That is the only evidence that an allocation is correct, and it is worth noticing that it is a completely different kind of evidence from the spill count on the same row.
This collection has been bitten by aligned(64) six times: a boundary that is off by one in the direction that makes an interval look shorter. The register-allocation version is an interference edge built from a half-open live range when the machine’s intervals are inclusive.
$ python3 compback.py --run | sed -n '/ value closed range/,/LOST 15/p'
value closed range half-open range
v0 [0, 12] [0, 11] <- the loss
v1 [1, 11] [1, 10] <- the loss
v2 [2, 8] [2, 7] <- the loss
v3 [3, 4] [3, 3] <- the loss
v4 [5, 14] [5, 13] <- the loss
v5 [6, 7] [6, 6] <- the loss
v6 [8, 9] [8, 8] <- the loss
v7 [9, 10] [9, 9] <- the loss
interference edges: closed 50, half-open 35, LOST 15
The direction matters and is not what a reader would guess. A half-open range is a subset of the correct one, so the buggy graph has fewer edges — which means it is easier to colour and more likely to succeed. And succeeding is the failure.
A document that said “half-open ranges are wrong” without saying which way would have taught its reader nothing, and the first version of cbreg.py’s own docstring did exactly that.
$ python3 compback.py --run | sed -n '/ phys correct alloc half-open alloc/,/IT RETURNED A NUMBER/p'
phys correct alloc half-open alloc VERDICT
1 WRONG correct the bug is INVISIBLE here
2 WRONG WRONG the bug CHANGED THE ANSWER
3 correct WRONG the bug CHANGED THE ANSWER
4 correct WRONG the bug CHANGED THE ANSWER
5 correct WRONG the bug CHANGED THE ANSWER
6 correct WRONG the bug CHANGED THE ANSWER
7 correct WRONG the bug CHANGED THE ANSWER
8 correct WRONG the bug CHANGED THE ANSWER
10 correct WRONG the bug CHANGED THE ANSWER
13 correct WRONG the bug CHANGED THE ANSWER
14 correct WRONG the bug CHANGED THE ANSWER
the half-open allocator produced a WRONG ANSWER at 10 of 11
pressures. §KEEP§AND IT DID NOT RAISE, DID NOT CRASH, AND DID NOT
PRINT ANYTHING ODD. §KEEP§IT RETURNED A NUMBER.
Ten of eleven pressures give a wrong answer. One gives the right one. And the sweep goes below the pressures the previous table used precisely because pressure 1 is the one at which the bug is invisible — a sweep that started at three would have reported nine of nine and called it detected.
The shape of a finding includes where it is not, and a finding with no hole in it is not yet a finding. This is the sentence that changed how this course reports. The number ten-of-eleven is more informative than eleven-of-eleven, and the way to get it was to look for the pressure where the bug does nothing rather than to sweep until it appeared everywhere.
And here is the finding that matters more than the count: the half-open graph has fewer edges, so it colours more easily, so it spills fewer values.
Coalescing merges a move-related pair when the two intervals do not overlap. With half-open ranges the source of a move at instruction i has a range ending at i−1 and the destination begins at i, so i−1 < i and the merge happens — while the source is live at i, because the move is its use.
$ python3 compback.py --run | sed -n '/ pressure merged(closed)/,/OPPOSITE FAILURES/p'
pressure merged(closed) unsound(closed) merged(half) UNSOUND(half) checksum
1 0 0 2 2 correct
2 0 0 2 2 WRONG
3 0 0 2 2 WRONG
4 0 0 2 2 WRONG
5 0 0 2 2 WRONG
6 0 0 2 2 WRONG
7 0 0 2 2 WRONG
8 0 0 2 2 WRONG
10 0 0 2 2 WRONG
13 0 0 2 2 WRONG
14 0 0 2 2 WRONG
§KEEP§NOTE THE DIRECTION IN THAT TABLE: THE INTERFERENCE-GRAPH BUG
LOSES EDGES, AND THE COALESCER BUG GAINS A MERGE. §KEEP§BOTH ARE THE
SAME OFF-BY-ONE AND OPPOSITE FAILURES, AND A READER WHO HAS ONLY SEEN
ONE OF THEM WILL NOT RECOGNISE THE OTHER.
Read the two tables beside each other. The interference-graph bug loses edges. The coalescer bug gains a merge. Both are the same off-by-one, and a reader who has only seen one of them will not recognise the other — which is the argument for printing both on the same page instead of one per course.
x86-64 runs on this host. This is the first course in the collection whose machine executes the code it makes, and so it is the first that can put a ratio on the cost of a spill. Every other number on this page is a count; this one is a cost.
Four arms, one function, four values forced through a stack slot. All four compute the same thing and all four must agree:
$ python3 compback.py --run | sed -n '/ arm spilled vs arm A checksum/,/FOUR UNKNOWNS/p'
arm spilled vs arm A checksum
A 0 1.00-1.25 5925179420309322629
B 1 1.00-1.25 5925179420309322629
C 2 1.00-1.25 5925179420309322629
D 4 1.25-1.56 5925179420309322629
ALL FOUR ARMS CARRY THE SAME CHECKSUM, so all four did the work,
and the comparison is between four programs that compute the
same number at different costs. §KEEP§A TIMING TABLE WHOSE ARMS
DISAGREE IS NOT A COMPARISON, IT IS FOUR UNKNOWNS.
Four arms, one checksum, four costs. That is a comparison. A timing table whose arms disagree is not a comparison — it is four unknowns, and the section says so in those words.
Read the band column again before you do anything else with it. Arms B and C — one spill and two spills — sit in the same band, and only arm D separates. The artifact does not leave that as a shape in a column; it states the verdict against a named reference and prints why:
$ python3 compback.py --run | sed -n '/ spilled vs arm A x arm A/,/THE COMPARISON THE REPORT MAKES/p'
spilled vs arm A x arm A vs the 1-SPILL arm
1 1.00-1.25 AT THE REFERENCE
2 1.00-1.25 INSIDE THE NOISE: not distinguishable from the 1-SPILL cost
4 1.25-1.56 ABOVE THE NOISE: clearly more than the 1-SPILL cost
§KEEP§THE VERDICT IS A RATIO AGAINST THE 1-SPILL ARM AND NOT A
§KEEP§COMPARISON AGAINST THE FLOOR, §KEEP§AND THE FLOOR IS STILL
§KEEP§PRINTED ABOVE BECAUSE IT IS THE HONEST STATEMENT OF HOW MUCH
§KEEP§TWO INDEPENDENT ESTIMATES OF ONE ARM DISAGREE. §KEEP§§KEEP§ON
§KEEP§THIS MACHINE, UNDER LOAD, THE FLOOR AND THE 4-SPILL
§KEEP§DIFFERENCE OVERLAP, §KEEP§SO "DIFFERENCE > FLOOR" IS NOT A
§KEEP§QUESTION THIS MACHINE ANSWERS THE SAME WAY TWICE. §KEEP§THE
§KEEP§4-SPILL ARM AGAINST THE 1-SPILL ARM IS, AND THAT IS THE
§KEEP§COMPARISON THE REPORT MAKES.
So there is no “cost of a spill” on this page, and there must not be one anywhere. One spill and two spills cost the same measurable amount here — they are indistinguishable from each other — and going to four costs more than twice what going to one did. A cost that is not linear is not a cost you can divide by a count. Any sentence of the form “a spill costs X” is unsupported by this artifact, and the reason is not pedantry: it is that the machine is hiding the first one or two inside its own scheduler, and the fourth is where it stops hiding it.
$ python3 compback.py --run | sed -n '/THE LADDER IS GEOMETRIC/,/COULD NOT DISTINGUISH THEM/p'
THE LADDER IS GEOMETRIC WITH RATIO 5/4, §KEEP§ RUNNING DOWNWARDS AS
WELL AS UP, §KEEP§§KEEP§AND THAT DOWNWARD HALF IS NOT COSMETIC: §KEEP§A
LADDER §KEEP§THAT ONLY GOES UP PUTS EVERY VALUE BELOW 1.00 IN THE SAME
FIRST §KEEP§BAND, §KEEP§SO 0.35 AND 0.88 -- A FACTOR OF TWO AND A HALF,
THE §KEEP§WHOLE POINT OF THE MEASUREMENT -- CAME BACK AS THE SAME
ANSWER. §KEEP§A BAND LADDER THAT CANNOT DISTINGUISH THE NUMBERS
YOU ARE ABOUT TO COMPARE IS NOT A ROUNDING, §KEEP§IT IS A LOSS
OF THE MEASUREMENT, §KEEP§AND IT FAILS QUIETLY.
The report prints a band rather than a number, and the exact ticks live in cbbench.out instead, for a reason that is worth stating plainly because it is the only reason this course’s timing can be committed at all:
And the clock itself was checked before it was trusted — measured twice, once busy and once across a 400 ms sleep, because a TSC is a fixed-rate counter and a tick is time only if the rate holds:
$ python3 compback.py --run | sed -n '/ TSC rate, busy/,/A DURATION BOUNDS A COUNT/p'
TSC rate, busy 2.2957 GHz
TSC rate, across sleep 2.2957 GHz
the two agree to within 0.01 per cent
§KEEP§AND A TICK IS TIME AND NOT CYCLES: §KEEP§NO NUMBER IN THIS COURSE
IS A CYCLE COUNT AND NONE IS CONVERTED INTO ONE.
Two rates, measured two ways, agreeing to within 0.01 per cent. So a tick is time and not cycles, and no number in this course is a cycle count and none is converted into one. That is a small sentence that prevents an entire class of dishonest arithmetic.
cbreg.build_interference on kernel_c with closed ranges and then without. Edges go from 50 to 35. The graph is easier, so it colours more easily, so it spills fewer. Every spill count in the allocator tables will look better with the bug in. Now read the checksum column: it says WRONG. That pairing is the whole exercise — a number that improved and a correctness verdict that got worse, from one character of interval notation.)cbreg.py and re-run all four kernels. Expect the “correct” column to go to no while the spill counts stay exactly where they were. A spill slot reused by a later value makes the end-of-program read the wrong number, and the allocation was right all along. This bug shipped in this artifact and it is worth reproducing once, because a test that is wrong in the safe direction trains you to distrust correct results.)cd courses/compback/assets/samples && ./build_samples.sh. Read cbbench.out first for the raw ticks and the two floors, then the verdict table in compback.out for the bands. Then check the thing that matters: are 1-spill and 2-spill separable on your machine? Here they are not. If they are on yours, the finding is about your machine and not about register pressure, and that is worth reporting rather than quietly accepting. Also look at the schedule comparison — hand-interleaving four independent chains came out below the comparison floor, and on a wide out-of-order core that is the expected result rather than a disappointment.)cbreg.py’s colouring allocator and change only its cost heuristic — spill the interval with the most uses inside a loop, or the one with the shortest remaining range. Re-run the totals. The number moves, the graph does not, and nothing about the algorithm changed. That is the demonstration behind the sentence “which allocator is better is a property of your corpus”, and it takes ten minutes.)Backwards, cb-isel produced the sequence this pass names values in. The shapes are the same and the trap is the same one pass later: 49 wrong machine forms did not fail, and a spill count that is too low does not fail either.a64-frame and x86-frame teach what a frame is once the allocator has decided there needs to be one — which is the subject of the next page in this course, because a backend has to know the callee-saved set before it allocates.
Across architectures, exe-latency is where you met that a store and a reload to the same slot is a round trip through the memory hierarchy. This page puts a ratio on it — and it is the first time this collection has done so, which is why the label on the timing table is different from the label on the allocator tables above it.
Forwards, cb-sched reorders what allocation produced and finds a schedule that is faster and wrong. And cb-verify reads this pass’s decisions back out of the finished bytes with no symbol table — and finds that it recovers the consequences, not the allocation.
Outward, three things this page deliberately does not claim. The complexity numbers are QUOTED and not measured: linear scan is O(n log n) and the interference graph is quadratic in the worst case, with the papers named, and this course measures neither because both are properties of the input size and this corpus is twelve instructions. Saying so is cheaper than measuring it and it is true. And the timing section’s own largest limit is the one worth carrying: the harness executes four hand-written bodies whose spill counts were decided elsewhere, so the number is the cost of the decision and not of a compiler that made it.
So the reusable lesson is narrow and specific, and it is the second time this collection has had to learn it: in register allocation, the metric points the wrong way under a whole class of bugs. Fewer spills means an easier graph, and an easier graph can mean a wrong one. Print the checksum, not just the count — and print where the bug is invisible, because a detector with no hole in it has not been tested.