Selection chose the instruction. Allocation chose the register. What is left is the order — and this is the pass that looks like an optimisation and is actually a legality pass, because a schedule that does not respect the dependencies is not a fast program, it is a different program.
The algorithm here is list scheduling, in full:
$ python3 compback.py --run | sed -n '/LIST SCHEDULING, in full/,/THIRD IS A THIRD POLICY/p'
LIST SCHEDULING, in full: while unscheduled nodes remain, take one with
no unscheduled predecessor, and among those take the one the PRIORITY
FUNCTION prefers. Three priorities, all measured:
index the input order, which is a SCHEDULE and the control
every other schedule is measured against
height longest chain STARTING at the node, ties to the LOWEST
index -- which on this kernel reproduces the input order
height_hi the SAME priority, ties to the HIGHEST index -- which on
this kernel produces a different order from `height` and
nothing else does
degree most UNSCHEDULED SUCCESSORS, which is a third policy
Three phases and they are not separable: build the dependency graph, ask what a node’s priority is, then repeatedly take the ready node the priority function prefers. Everything interesting on this page is in one of those three phases, and the phase most textbooks spend least time on is the first.
$ python3 compback.py --run | sed -n '/ THE KERNEL IS kernel_d/,/CONCLUDES THAT SCHEDULING WORKS/p'
THE KERNEL IS kernel_d, 16 instructions, and §KEEP§IT IS NOT kernel_a:
§KEEP§kernel_a IS A DEPENDENCY CHAIN, ITS CRITICAL PATH EQUALS ITS
LENGTH, AND EVERY SCHEDULE OF IT IS THE INPUT ORDER -- §KEEP§SO A
SCHEDULER MEASURED ON IT HAS NOTHING TO DECIDE. §KEEP§A LIST SCHEDULER
THAT IS GIVEN NO CHOICE PRINTS THREE COPIES OF THE INPUT AND A
READER WHO HAS NOT SPOTTED IT CONCLUDES THAT SCHEDULING WORKS.
This is worth more than any number on the page.kernel_a is a dependency chain: its critical path equals its length, so every legal schedule of it is the input order. Run a list scheduler on it and it prints three copies of the input. A reader who has not spotted that concludes scheduling works, because the output is stable and reproducible and the checksum never moves.
That is the failure mode to carry out of this page: an experiment with no variance proves nothing, and a scheduler given no choice produces none. The kernel below is 16 instructions with a critical path of 8 and ILP 2.00, so there is genuinely room to move things.
$ python3 compback.py --run | sed -n '/WITHOUT memory dependencies: critical path/,/THE ONLY THING THAT SEPARATES THE FOUR/p'
WITHOUT memory dependencies: critical path 8 of 16 instructions, ILP 2.00
priority order illegal checksum
index [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 0 same
height [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 0 same
height_hi [3, 2, 1, 0, 5, 4, 7, 6, 10, 9, 8, 12, 11, 13, 14, 15] 0 DIFFERENT
degree [0, 1, 2, 4, 6, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15] 0 DIFFERENT
Four orders, all legal, zero illegal reorders in any of them. And height reproduces the input order exactly while height_hi does not — and they are the same algorithm.
$ python3 compback.py --run | sed -n '/§KEEP§AND `height` AGAINST `height_hi`/,/BREAKING IT TOWARD THE HIGHEST/p'
§KEEP§AND `height` AGAINST `height_hi` IS THE MOST IMPORTANT ROW IN
THAT LIST, §KEEP§BECAUSE THEY ARE THE SAME ALGORITHM WITH A DIFFERENT
UNDOCUMENTED TIE-BREAK, §KEEP§AND EVERY LIST SCHEDULER IN EVERY
TEXTBOOK BREAKS TIES BY SOME RULE AND NONE OF THEM SAY WHICH. §KEEP§A
BACKEND THAT REPORTS "MY SCHEDULER IS BETTER" WITHOUT NAMING THE
TIE-BREAK HAS REPORTED A DIFFERENT SCHEDULER AND NOT A BETTER ONE.
Same priority function, opposite tie-break, different schedule. Every list scheduler in every textbook breaks ties by some rule and none of them say which. So the sentence “my scheduler is better” without naming the tie-break is reporting a different scheduler and not a better one — and this is the same class of mistake as the register-allocation page’s spill policies: a comparison that does not name the decision it is not varying has compared two configurations and called it an algorithm.
Mechanically it is simple. The four initial movs have the same downstream height, so breaking the tie toward the lowest index reproduces the input order and breaking it toward the highest produces its reverse on the first four instructions and nothing else.
And the checksums differ between the four. That is not a bug, and the artifact explains it in the same breath as the verdict:
$ python3 compback.py --run | sed -n '/AND THE CHECKSUM DIFFERS BETWEEN THEM/,/THE ARGUMENT FOR HAVING BOTH/p'
§KEEP§AND THE CHECKSUM DIFFERS BETWEEN THEM, §KEEP§WHICH IS NOT
A BUG: §KEEP§IT IS A FOLD OVER THE VALUES *IN SCHEDULED ORDER*,
§KEEP§AND TWO LEGAL SCHEDULES OF THE SAME PROGRAM DEFINE THEIR
VALUES IN A DIFFERENT ORDER. §KEEP§§KEEP§THAT IS EXACTLY WHY A
FOLD THAT IGNORED THE ORDER COULD NOT HAVE DETECTED THE
ALIASING TRAP, §KEEP§AND IT IS THE ARGUMENT FOR HAVING BOTH.
Read that last sentence carefully, because it is the course’s position on evidence stated once and it applies everywhere. A fold that ignored the order could not have detected the aliasing trap — the trap on the next page — so having both checks is not redundancy. One says “legal”, the other says “correct”, and they are different claims.
Here is the failure this pass is most likely to produce, and it is worth being precise about why it is not a bug in the scheduler.
The kernel stores to [1024+8] and then loads from [1024+8]. The same address, so the dependency is real, and a scheduler that does not know they alias will hoist the load above the store.
$ python3 compback.py --run | sed -n '/ memory deps priority order/,/WRONG ANSWER/p'
memory deps priority order checksum VERDICT
WITH index [0, 1, 2, 3, 4, 5, 6, 7] 6601140724 correct
WITH height [0, 1, 2, 3, 4, 5, 6, 7] 6601140724 correct
WITH height_hi [1, 0, 2, 3, 4, 5, 6, 7] 10036638844 WRONG ANSWER
WITHOUT index [0, 1, 2, 3, 4, 5, 6, 7] 6601140724 correct
WITHOUT height [0, 1, 2, 3, 5, 6, 4, 7] 6601062688 WRONG ANSWER
WITHOUT height_hi [1, 0, 2, 5, 3, 6, 7, 4] 10034139088 WRONG ANSWER
Three wrong answers, and notice that the WITH-memory-dependency height_hi row is wrong too — so this is not only “the scheduler dropped an edge”. It is: a tie-break plus a dependency builder can move an instruction across a real dependency even when the memory edges are all present.
And then the row that settles what the wrong rows actually mean. The same height schedule, run on distinct addresses, where the reorder is legal:
$ python3 compback.py --run | sed -n '/the same schedule on DISTINCT addresses/,/IS THE WORST COMBINATION THIS/p'
the same schedule on DISTINCT addresses, where the reorder is
legal:
WITHOUT height [0, 1, 2, 3, 5, 6, 4, 7] 6601062688 correct
The exact same schedule, checksum 6601062688, is wrong on one kernel and correct on the other. The only difference between the two kernels is whether the backend knew the addresses aliased.
That distinction is worth its cost. A scheduler that drops an unknown memory dependency is not wrong; it is a scheduler without an alias analysis. Every production compiler makes this choice deliberately, and the difference between the choices is not correctness — it is how many times the answer will be right on code you did not write.
$ python3 compback.py --run | sed -n '/§KEEP§AND TIMING WILL NOT CATCH IT/,/IT IS A LIE THAT HAPPENS TO POINT DOWN/p'
§KEEP§AND TIMING WILL NOT CATCH IT. §KEEP§IF THE ONLY MEASUREMENT
WERE HOW FAST THE TWO SCHEDULES ARE, THE BROKEN ONE WINS. §KEEP§THE
ONLY THING THAT CATCHES IT IS A VALUE, WHICH IS WHY EVERY SCHEDULE
IN THIS FILE IS EVALUATED AND ITS CHECKSUM PRINTED BESIDE ITS
LENGTH. §KEEP§THIS IS THE GENERAL FORM OF EVERY TIMING BUG IN THIS
COLLECTION AND IT IS WORTH NAMING: A FASTER WRONG ANSWER IS NOT A
SMALLER NUMBER, IT IS A LIE THAT HAPPENS TO POINT DOWN.
A faster wrong answer is not a smaller number; it is a lie that happens to point down. That is the general form of every timing bug in this collection, and this page is where it is sharpest, because the failure mode it produces is faster and wrong — the worst combination. A slower wrong answer gets caught in a test suite the first time. A faster one gets shipped.
The fifth bug in this collection that lived in the failure branch. The dependency builder skipped every instruction with no destination — which is every store. So the memory-ordered schedule reordered stores across the very things that compute their data. The schedule that was supposed to catch the aliasing bug was the schedule that carried it. A check that runs only when something has already gone wrong cannot be the thing that notices; and a builder that walks instructions and asks “does this one have a destination?” has quietly decided that stores are not instructions.
$ python3 compback.py --run | sed -n '/§KEEP§AND THE FIRST VERSION OF THIS FILE COMPUTED ONLY THE LONGEST/,/THE WHOLE OF THE PRIORITY FUNCTION/p'
§KEEP§AND THE FIRST VERSION OF THIS FILE COMPUTED ONLY THE LONGEST
CHAIN *ENDING* AT EACH NODE AND USED IT AS THE PRIORITY -- §KEEP§SO THE
SCHEDULER PREFERRED THE NODES WHOSE WORK ARRIVED LATEST, WHICH IS THE
EXACT OPPOSITE OF WHAT HIDES LATENCY. §KEEP§IT PRODUCED A SCHEDULE, IT
WAS LEGAL, IT WAS DETERMINISTIC, AND IT WAS NO BETTER THAN THE INPUT
ORDER. §KEEP§THE TWO HEIGHTS ARE NOW COMPUTED AND THE DISTINCTION IS
THE WHOLE OF THE PRIORITY FUNCTION.
Read that again: it produced a schedule, it was legal, it was deterministic, and it was no better than doing nothing. A wrong priority function is not a crash, a wrong answer, or a hang. It is a scheduler that runs. That is now retraction R9’s sibling on this page, and the two heights are computed and named because the distinction between them is the priority function.
kernel_a instead of kernel_d. Expect all three priorities to print the identical input order, with zero illegal reorders and identical checksums. Now run kernel_d. The difference between those two runs is not a property of the scheduler; it is a property of whether you gave it anything to decide. If your own test suite runs only on chains, you are shipping a scheduler you have never tested.)height to break ties toward the highest index instead of the lowest, which is exactly what height_hi is. Re-run. Expect the order to change on the first four instructions and nowhere else, and the checksum to change with it because the fold is over values in scheduled order. Nothing about the priority function changed — only the tie-break — and that is the whole argument for naming tie-breaks in any scheduler comparison you read or write.)6601140724 to 6601062688 while the edge count falls by one. Then time both and watch the broken one win. That is the exercise: build the trap, then observe that the measurement a reader would naturally reach for endorses it.)-O2, then at -O0. Where the order changes, the answer is in an alias analysis; where it does not, the conservative path was taken. The number of places you find is the real cost of that choice, and it is a fact about your program rather than about the compiler, which is the reason no course in this collection can measure it for you.)Backwards, exe-latency derived why a dependency chain costs you what it costs, and exe-deps is where out-of-order execution and the rename table were introduced. This page deliberately does not repeat either: the question here is not whether reordering helps a machine but whether the compiler is allowed to do it, and the aliasing kernel answers the second question rather than the first. exe-speculate covers the other direction — speculation past a branch the compiler did not reorder.
Across architectures, a64-order and x86-order taught the architectural guarantee: what the hardware promises once the compiler has emitted the order. Read them beside this page and the difference is the whole subject of scheduling. Those courses asked what the machine guarantees about the order you chose. This one asks which order you were allowed to choose in the first place, and the answer is “any order whose dependencies you can prove, and only those”.
Forwards, cb-abi is the fourth thing a backend must know before it emits anything, and it is a constraint of a different kind: not “what order is legal” but “which registers exist at all”. cb-verify then reads all of this back out of the finished bytes.
Outward, two limits and they are both printed in the artifact rather than implied. The schedule here is measured as a checksum and a critical path and never as a time, because the only schedule that could be timed is one the machine has already reordered — and cb-regalloc measures that instead, and reports that the difference was below the comparison floor. And the aliasing trap is constructed, not discovered: the two kernels differ by one literal address, so the experiment shows that a scheduler without an alias analysis is wrong, and it says nothing about how often a real one would be. A constructed trap is a demonstration and not a rate, and the distinction is the reason the experiment can be run on a build machine at all.
And the general form, which is the third time this collection has needed it: the check that lives in the failure branch is invisible on a healthy run. That is how the store-edge bug survived, how the cross-check’s classifier stayed in a path a passing run never reaches, and how this course’s own dead normalisers stayed dead until someone pre-seeded a fire table and printed the zeros. Print the rows that fired zero times. A rule that never fired is a row, not an absence.