Loading page…
Master the fundamental concepts of code generation through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksIR temporaries outnumber physical registers. The classic approach builds an interference graph (nodes are temporaries, edges mean simultaneous live ranges) and colors it with K colors for K registers. Chaitin-Briggs allocation in GCC and LLVM spills uncolorable nodes to the stack.
Compute live ranges via dataflow. Build interference graph. Simplify and spill: nodes with degree less than K can be colored. Spill expensive nodes to memory. Emit mov loads/stores around spilled uses.
cLoading…
Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.
You will implement register allocation using graph coloring on your IR. This exercise requires building the interference graph, coloring nodes, and inserting spill code when more temporaries are live than available registers.
Allocate registers by graph coloring: compute liveness, build the interference graph, then simplify and select (Chaitin's algorithm with Briggs' optimistic spilling). Every step is printed, so each one can be checked.
The first line is registers K. Then straight-line TAC, one instruction per line:
cLoading…
Operands are variable names or integer literals. A variable used before any definition is an incoming value (like a parameter), live on entry.
Variables are ordered by first appearance, reading each instruction left to right (x = a + b → x, a, b). "Lowest" below always means earliest in this order.
live-in = uses ∪ (live-out − def).d, add an edge between d and every other variable in its live-out. Also, all variables live into instruction 0 interfere with each other. (No special case for copies.)< K, pushing it on a stack. If every remaining node has degree ≥ K, remove the node with the highest current degree (ties: lowest) as a potential spill and push it too.r1…rK not used by an already-coloured neighbour. If none is free, it is an actual spill.cLoading…
Input:
cLoading…
Output:
cLoading…
Hidden tests cover a long chain that fits in two registers and a real spill with K = 2. (For straight-line code the interference graph is an interval graph, so simplify only gets stuck when K + 1 values really are live at once: the optimistic push then always ends in an actual spill.)