Five pages of this course measured decisions: which machine form, which register, which order, which contract. All of them were made by a program you could read. None of them left a trace in the output you would ship. A shipped binary has no selector, no allocator and no scheduler in it. It has bytes.
So here is the question that turns the whole course into something you can use: given a function with no symbol table and no debug information, what can you recover — and how do you know which of your four answers was a measurement?
$ python3 compback.py --run | sed -n '/THE ARTIFACT. Given a compiled function/,/a reading can be checked/p'
THE ARTIFACT. Given a compiled function with no symbol table and no
debug information, recover:
1. how many instructions it contains,
2. how many of them touch memory,
3. its APPARENT REGISTER PRESSURE -- the number of distinct
registers live at the busiest point,
4. and what that implies about the allocator that produced it.
§KEEP§AND (4) IS THE ONLY ONE OF THE FOUR THAT IS AN INFERENCE, AND
IT IS LABELLED AS ONE. §KEEP§THE FIRST THREE ARE COUNTS AND THE
FOURTH IS A READING, AND THE DISTINCTION IS THE WHOLE POINT OF
THIS SECTION: §KEEP§A COUNT CAN BE CHECKED AND A READING CANNOT.
Read that last line twice, because it is the discipline of the entire page and it is not a stylistic preference. A count can be checked and a reading cannot. Anyone can re-run the instruction count and get the same number. Nobody can re-run an inference and get the same inference, because an inference has a step in it where a person had to think — and the person’s conclusion is not in the binary.
Three counts and one reading, labelled apart, is the difference between a tool and a story. A backend profiler that prints four numbers with no indication of which are recomputable is not measuring anything — it is asserting four things and checking none. The artifact labels item 4 in the artifact’s own text before it prints a single figure, and this page follows the same rule in every block below.
Every figure in this table is MEASURED: words were emitted by a real compiler, read back by a disassembler this course drives itself, and counted. Six rows, three targets, two optimisation levels.
$ python3 compback.py --run | sed -n '/ target level instructions headers mem ops/,/ riscv64 O2/p'
target level instructions headers mem ops distinct regs
x86_64 O0 235 11 141 5
x86_64 O2 253 11 37 6
aarch64 O0 265 11 136 6
aarch64 O2 190 11 11 12
riscv64 O0 329 11 173 9
riscv64 O2 207 12 6 8
There is an enormous amount in that table and almost none of it is what a reader expects. Instruction count goes up from -O0 to -O2 on two of the three targets — 235 to 253 on x86-64, 265 down to 190 on AArch64, 329 down to 207 on RISC-V. And the register count goes the wrong way too: 5 to 6 on x86-64, 6 to 12 on AArch64, 9 to 8 on RISC-V. Every reader coming out of the previous five pages expects the optimised build to be smaller in every column. It is not, and the column that moved most is the one that moved the hardest to read: 141 memory operations down to 37.
The memory-operation column is the real signal, and the reason is the subject of cb-ir: -O0 spills every argument to the stack and -O2 keeps a leaf in registers. 141 loads and stores against 37 is not an optimisation, it is the difference between a function that talks to memory and a function that does not. The instruction count rises while the function gets faster, because the instructions it gained are SIMD ones that do four lanes at a time — and if your profiler reported only instruction count, -O2 would look like a regression.
Now the fourth item, for one function, and note that the reasoning is printed with it rather than beneath it:
$ python3 compback.py --run | sed -n '/THE INFERENCE, for one function/,/VISIBLE IN A/p'
THE INFERENCE, for one function, and the reasoning is printed with it:
function leaf
instructions 9
distinct regs 7
peak at one 3 registers, at instruction 3
§KEEP§AND WHAT THAT IMPLIES IS A READING, NOT A COUNT:
§KEEP§A LEAF WITH 9 INSTRUCTIONS THAT NEVER TOUCHES THE STACK AND
PEAKS AT 3 DISTINCT REGISTERS WAS ALLOCATED WITHOUT SPILLING, AND
§KEEP§A COMPARISON WITH THE -O0 BUILD OF THE SAME SOURCE IS WHAT
TURNS THE READING INTO AN INFERENCE, AND §KEEP§THE DIFFERENCE
BETWEEN THE TWO IS THE ALLOCATOR'S WORK AND NOTHING ELSE'S.
-O0 build of the same leaf: 23 instructions, 15 of them touching
rsp or rbp -- which is the PROLOGUE, and §KEEP§A PROLOGUE IS
§KEEP§THE ONE PLACE A REGISTER ALLOCATION IS VISIBLE IN A
DISASSEMBLY WITHOUT ANY DEBUG INFORMATION AT ALL.
Nine instructions, seven distinct registers, peaking at three live at instruction 3 — and a comparison with 23 instructions and 15 stack references at -O0. The difference between the two builds is the allocator’s work and nothing else’s, because the source is the same and the instruction selection is nearly the same shape. That is what turns a reading into an inference, and it is why the -O0 build is in the block at all: without a second build to compare against, “peaks at 3 registers” says nothing about spilling, because you do not know what the pressure would have been.
And note what is not claimed. The artifact does not say the -O2 leaf was allocated well. It says it was allocated without spilling, and that is a completely different sentence — the first is a judgement about quality and the second is a count of what did not happen.
Three limits, and the second is the one that changes how you build the tool:
$ python3 compback.py --run | sed -n '/WHAT THIS SECTION CANNOT DO, and it is a real limit/,/no bit says which/p'
WHAT THIS SECTION CANNOT DO, and it is a real limit:
* it cannot recover the ALLOCATION, only its CONSEQUENCE. Two
different allocations can produce the same instruction count and
the same memory-op count and differ in speed.
* it cannot tell a SPILL from a deliberate MEMORY REFERENCE. §KEEP§A
STORE TO [rsp+8] WITH NO FRAME IS A SPILL; A STORE TO [rdi+8] IS
THE PROGRAM. §KEEP§WITHOUT THE FRAME, THEY LOOK LIKE EACH OTHER,
AND THAT IS WHY THE FRAME IS THE SIGNAL AND NOT THE STORE.
* it cannot distinguish a COALESCED MOV from one the compiler chose
to keep, because both are one instruction and no bit says which.
The second bullet is the design. If you try to detect spills by looking for stores to a stack slot, you are looking at movq %rdi, -0x8(%rbp) — which is a spill — and at movq %rax, 8(%rdi) — which is the program storing to an array the caller passed in. The two are the same instruction shape. The only thing that separates them is that one of them is near a frame and the other is not.
That retraction is R14 in the artifact’s list of eighteen, and it is the one a backend author is most likely to get wrong — because the intuitive reading of a prologue is “the places it saves registers” and the correct reading is “the place it made a frame”. Retraction R14 says it plainly: it is visible because it is a frame; the registers it saves are the allocator’s business and the compiler may save more than it modified.
The first bullet is the one that should govern how you name the tool. You are recovering consequences, not the allocation. Two different allocations can produce the same instruction count, the same memory-op count and the same register count and differ in speed — and there is no bit anywhere in the binary that says which one it was. That is R13, and it is the sentence this course wants you to carry out of the last page.
Everything above is MEASURED. Everything the other five pages quote about three architecture manuals is QUOTED. Those are different kinds of knowledge and the boundary between them is not a disclaimer — it is a table, and the count is printed with it, because a percentage in a sentence is a number nobody can check.
$ python3 compback.py --run | sed -n '/^ 25 rows:/,/ON EITHER SIDE/p'
25 rows: 8 MEASURED, 9 MEASURED-ON-BYTES, 8 QUOTED
32 per cent is QUOTED, and §KEEP§THAT NUMBER IS SMALLER THAN THE
x86-64 SECTION'S AND THE COMPARISON IS PRINTED BOTH WAYS BECAUSE
§KEEP§SAYING "THIS COURSE QUOTES LESS" WITHOUT THE OTHER NUMBER
WOULD BE A COMPARISON WITH NO DENOMINATOR ON EITHER SIDE.
25 rows: 8 MEASURED, 9 MEASURED-ON-BYTES, 8 QUOTED. Thirty-two per cent quoted — and that is the smallest quoted fraction of any course in this collection, which is a fact about the subject and not about the author. A compiler backend is the one place in this collection where a machine can be asked a question, and x86-verify holds the other number. The honest sentence is the two-way comparison, because saying “this course quotes less” without the other number is a comparison with no denominator on either side.
And the rows a reader is most likely to mistake for measurements are marked in the table itself:
$ python3 compback.py --run | sed -n '/AND THE THREE ROWS THAT ARE QUOTED/,/AND IT IS TRUE/p'
AND THE THREE ROWS THAT ARE QUOTED *AND* NOT MEASURED ARE MARKED,
because they are the rows a reader is most likely to mistake for
measurements:
NOT MEASURED HERE
NOT MEASURED HERE
§KEEP§THE COMPLEXITY CLAIMS ARE THE ONES THAT MATTER MOST AND THE
ONES THIS COURSE MEASURED LEAST, BECAUSE MEASURING THEM PROPERLY
NEEDS A CORPUS OF THOUSANDS OF INSTRUCTIONS AND THIS ONE HAS TWELVE.
§KEEP§SAYING THAT IS CHEAPER THAN BUILDING THE CORPUS AND IT IS
MORE USEFUL, BECAUSE A READER WHO BELIEVED THE COMPLEXITY CLAIM
BECAUSE IT WAS IN A TABLE WOULD BE WRONG IN A WAY NOBODY WOULD
NOTICE.
And here is a defect in this very block, and it is worth more than the block. The header says three rows are marked. The block prints two lines reading NOT MEASURED HERE. You can check it: grep -c "NOT MEASURED HERE" compback.out returns six occurrences in the whole file, two of which are in this table and two of which are in the complexity rows’ own source lines. A count that does not add up, in the one section whose entire subject is counts that add up. Every other number on this course has been checked; this one has not, and it shipped.
It is not repaired here, deliberately. The pages read the artifact, and a page that silently corrected a recorded figure would be worse than one that quoted it — because the correction would be invisible and the artifact would go on being wrong. The two unmarked rows are the complexity claims, and their reasoning is stated in the paragraph underneath: measuring them properly needs a corpus of thousands of instructions and this one has twelve.
A boundary page that hides a boundary defect is the worst kind of boundary page. This is the collection’s own recurring shape applied to itself. A label rendered two ways is not a label; a count that does not add up is not a count; and a summary line that disagrees with the table it summarises is the failure mode of every harness in this codebase that has ever counted the wrong thing and printed a clean result. The generalisation is already written down next door in rv-boundary:a percentage in a sentence is a number nobody can check — and a header sentence that says “three” above a table that marks two is the same defect one level up.
Before the table can be believed there are three things to run, and they are the last mechanical half of the course:
$ python3 compback.py --run | sed -n '/ Two readers over every word of the aarch64 leaf/,/IT IS A ROW WITH A ZERO AND NOT AN ABSENCE/p'
Two readers over every word of the aarch64 leaf: 9 words, 9 agree,
0 disagree, and the disagreements are printed above rather than
summarised. §KEEP§THE THREE THAT REMAINED IN AN EARLIER VERSION OF
THIS SECTION WERE PURELY PRINTING CONVENTIONS -- `lsl, #1` against
`lsl #1`, and `#0x6` against `#6` -- §KEEP§AND THE FIRE TABLE IS WHAT
MADE THEM VISIBLE, BECAUSE A DISAGREEMENT YOU CANNOT CLASSIFY IS A
DISAGREEMENT YOU CANNOT FIX.
THE NORMALISER FIRE TABLE, PRE-SEEDED WITH EVERY RULE NAME:
collapse space 0
comma before shift or immediate 10
hex immediate 1
mnemonic case 16
drop register size suffix 0 NEVER FIRED -- BY DESIGN
sp alias 0 NEVER FIRED -- BY DESIGN
6 rules, 3 fired, 3 matched nothing.
THE DEAD ONES: collapse space, drop register size suffix, sp alias
Nine words, nine agreeing, zero disagreeing — and the three that disagreed in an earlier version were commas and radixes. A disagreement you cannot classify is a disagreement you cannot fix, and the fire table is what makes them classifiable: ten of the twelve firings are the comma rule, and one is the radix. The table exists so that a rule which never fires is a row with a zero rather than an absence.
And two of the three dead rules are dead by design and say so in the table itself, which is the inversion this course needed. drop register size suffix and sp alias never fire here because the corpus does not exercise them — and a rule that normalises away the difference between an x8 and a w8 makes the whole comparison vacuous, reporting zero disagreements over a corpus where every word disagrees. That is the class of bug that reads as success.
The counter also counts a rule firing when it changes either side, not only this file’s rendering, and the reason is the sharpest line in the artifact: “a fire table that counts one side is a table of how often we print things a certain way.” The first version applied every rule to one side only, so hex immediate never fired — for the reason the rule was written to fix.
$ python3 compback.py --run | sed -n '/^ ALL FOUR FIRED/,+1p'
ALL FOUR FIRED: yes
The four deltas, and each one names the number it claims to move:
$ python3 compback.py --run | grep -E 'DELTA:|HIDDEN\.$|5 of 9 reported'
DELTA: misroutes -1, checksum changed YES
DELTA: edges -15, checksum changed YES
DELTA: edges -1, and the poisoned schedule gives A DIFFERENT ANSWER
DELTA: 5 of the 9 planted disagreements were HIDDEN.
Read those four numbers as a set, because the set is the argument. Poison 2 is the one that matters: edges -15and the checksum went wrong. A poison that only checked “did anything move” would have passed on a delta of +1 and would have missed the direction entirely — and here the direction is the finding, because the bug removes edges, makes the graph easier, and reports a better spill count. That is why the verifier for this course requires the sign of the edge delta and not only that something moved.
And poison 4 is the class of bug that reads as success: nine real disagreements are planted in the text the check compares, a normaliser that keeps the mnemonic and the first operand and discards the rest is added, and the broken check reports 4 of 9. Five of nine failures were hidden by a rule that made the two readers agree by deleting the same operand from both — so the agreement became evidence about the normaliser rather than about either decoder.
leaf.c at -O2 and at -O0, count instructions, memory operations and distinct registers for both, and compare against the table on this page. Then compile at -O1 as well, which is in the corpus but not in the six rows. Write down which of your four numbers changed and which did not. The instruction count moves and the memory-op count moves faster, because that is where the allocation is visible — and a fingerprint that reported only instruction count would have reported -O2 as bigger.)-Os build, which omits the frame far more aggressively than -O0 does, and see how many stores you are left with that you cannot name.)grep -c for each of MEASURED, MEASURED-ON-BYTES and QUOTED in compback.out, and compare the first figure with the second. A label rendered two ways is not a label. Then find the block in section 12 whose header says three and whose table marks two, and work out whether any other count in the file disagrees with its own header — that is the exercise, because it is the one that found this defect, and a boundary page is only as trustworthy as the last count on it.)Backwards, this page reads all five of its predecessors out of the finished bytes, and the two most interesting results are cross-checks rather than readings. -O2 emits more instructions than -O0 on two of three targets and far fewer memory operations — which is cb-ir’s finding (-O0 spills every argument) showing up as a column. And a leaf that peaks at three registers was allocated without spilling — which is cb-regalloc’s subject, recovered from the consequence rather than from the allocator. cb-abi is the page whose frame this one finds.
Across architectures, the decoders that do the reading are borrowed rather than forked, and rv-boundary is the model for the shape of this page — rvdec.py and a64dec.py come from rv-verify and a64-verify, written for other courses and edited not at all. obj-verify is where the collection established that a decoder naming every word and getting one wrong is worse than one that says which half of the format it implements, and that is why the fire table above prints its dead rules rather than hiding them.
Forwards out of the whole course, the habit rather than the technique: label a count as a count and a reading as a reading, and print the second one with its reasoning attached. That is the whole of section 11 in one sentence, and it is why a reader can use the four numbers above even knowing that only three of them are recomputable. obj-relocations and link-order are the next link in the chain and neither of them cares how you got here — which is the argument for having an IR, stated as a fact about the rest of this collection.
Outward, the boundary as a scope statement rather than an apology. 15 numbered limits, then 11 things a reader therefore cannot conclude beside 11 they can — and the second list being the longer one is the finding, because a course that printed only a cannot-list teaches its reader that the subject is unknowable, which is the opposite of what 17 measured bit patterns are for. Two of the eleven on the cannot side are the ones a reader is most likely to carry in the wrong direction: that the fingerprint recovers the allocation (it recovers consequences) and that anything here is a performance claim about AArch64 or RISC-V (neither of them ran).
And the last thing this page owes you is retraction R16, which is a retraction of this course’s own roadmap claim. It ticks the Compiler Debug Information item in docs/courses-todo.md, and it ticks the second half of it — reading a backend’s decisions out of the bytes — and not the first. Nothing here emits DWARF; the dwarf course owns the format. What this course adds is the question that comes before the format: what can you know about a compiler when you have no debug information at all? That is a smaller question and, on this host, a reachable one, and it is why the item can honestly be ticked at all.