Loading page…
Master the fundamental concepts of optimizations 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 worksBefore full graph coloring, linear scan allocation sorts live intervals by start point and assigns registers greedily. LLVM's fast -O0 path and many JIT compilers use simpler schemes. Understanding basics clarifies why spills happen.
Compute live interval for each temporary. Sort by start. Maintain active set of intervals currently in registers. When registers are full, spill the interval ending latest.
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 basic register allocation with live intervals. This exercise requires tracking when temporaries are live and assigning a fixed number of physical registers with spill fallback.
Allocate registers with linear scan (Poletto & Sarkar), the fast allocator used by JIT compilers: compute a live interval per variable, sweep the intervals in order of their start, and spill the interval that ends furthest away when registers run out.
The first line is registers K. Then straight-line TAC, one instruction per line, numbered from 0:
cLoading…
Operands are names or integer literals. Variables are ordered by first appearance, reading each instruction left to right (x = a + b → x, a, b).
For each variable v: start is the index of the first instruction that defines it, or 0 if it is used before any definition (an incoming value). end is the index of the last instruction that uses it, or its start if it is never used.
Process intervals by increasing start (ties: first-appearance order). Keep an active list of intervals currently holding registers, ordered by increasing end (ties: the one added first comes first). For each interval i:
end < start(i). (Strictly less: a value last used at instruction 5 still occupies its register at 5.)K registers are in use, give i the lowest-numbered free register r1…rK and add it to active.s be the active interval with the largest end (the last one in the list). If end(s) > end(i), i takes s's register and s is spilled: print spill S (for I). Otherwise i itself is spilled: print spill I.cLoading…
Input:
cLoading…
Output:
cLoading…
When c starts, both registers are busy; the active interval ending furthest is a (end 3), which does not end later than c (also 3), so c itself is spilled. At instruction 3 b has expired, and d reuses its register.
Hidden tests cover several incoming values that all start at 0, a spill that steals a register from a longer interval, and a program that fits without spilling.