THE FOLD / BOSS / THE CHOKE POINT / THE REGISTER ALLOCATION
THE REGISTER ALLOCATION
memory traffic you never wrote
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Two values that are alive at the same moment cannot share a register. Draw that as a graph and the question becomes exactly graph colouring — and when the colours run out, something goes to memory.
LIT verified live. 7 variables with overlapping live ranges give 8 interference edges and a maximum degree of 4. At most 3 are ever live at once. With 1 register there are 4 spills; with 2, 1 spill; with 3, none. The register count that suffices equals the maximum simultaneously live — here the greedy colouring finds the bound rather than merely approaching it.
LIT verified live. 7 variables with overlapping live ranges give 8 interference edges and a maximum degree of 4. At most 3 are ever live at once. With 1 register there are 4 spills; with 2, 1 spill; with 3, none. The register count that suffices equals the maximum simultaneously live — here the greedy colouring finds the bound rather than merely approaching it.
2 HOW IT WAS WEAVED · AI + HUMAN
Register allocation as graph colouring is Chaitin’s (1981); colouring is NP-complete in general, which is why real allocators are heuristics with a spill path.
AVAN (AI) computed the maximum simultaneously live separately from the colouring, so the two can be compared. They agree at 3. That agreement is not guaranteed — greedy colouring can need more than the clique number — and reporting them apart is the only way to see whether it did.
AVAN (AI) computed the maximum simultaneously live separately from the colouring, so the two can be compared. They agree at 3. That agreement is not guaranteed — greedy colouring can need more than the clique number — and reporting them apart is the only way to see whether it did.
3 ONE DIMENSION
Seven live ranges, and where they collide.
4 TWO DIMENSIONS · INTERACTIVE
Take registers away and watch the spills appear.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: overlapping lives, finite seats.
AVAN’s addition (the inverse-companion): the forward reading is that register allocation assigns variables to registers. The inverse is that a spill is a memory access appearing in a program that never wrote one. The source contains no load and no store; the allocator inserts them because it ran out of seats, and their cost is invisible in the code you are reading. Read backwards, the fastest thing a compiler can do for you is arithmetic you never see, and the slowest thing it can do to you is memory traffic you never wrote.
LIT 7 variables with overlapping live ranges give 8 interference edges and a maximum degree of 4 while at most 3 are ever live at once, so 1 register produces 4 spills, 2 registers 1 spill and 3 registers none - the count that suffices equals the maximum simultaneously live, meaning the greedy colouring found the bound rather than merely approaching it
FIG Register allocation as graph colouring is Chaitin's (1981); colouring is NP-complete in general, which is why real allocators are heuristics with a spill path. AVAN computed the maximum simultaneously live separately from the colouring so the two can be compared. They agree at 3. That agreement is not guaranteed - greedy colouring can need more than the clique number - and reporting them apart is the only way to see whether it did.
FIG Register allocation as graph colouring is Chaitin's (1981); colouring is NP-complete in general, which is why real allocators are heuristics with a spill path. AVAN computed the maximum simultaneously live separately from the colouring so the two can be compared. They agree at 3. That agreement is not guaranteed - greedy colouring can need more than the clique number - and reporting them apart is the only way to see whether it did.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN