Register Allocation (Graph Coloring) and Spill Cost TODO
Concept
Register allocation is the stage that maps an intermediate representation with an unbounded number of virtual registers onto the k actual physical registers available. Treating each simultaneously live value as a vertex and connecting values whose live ranges overlap with an edge produces an interference graph, turning the problem into graph k-coloring; since k-coloring a general graph is NP-complete, compilers use Chaitin-style heuristics (push vertices with degree < k onto a stack, then pop and color them back). A value that fails to get a color is spilled to memory, and spill cost is typically estimated with a heuristic like access count weighted by loop-nesting depth, divided by degree. In SSA form the interference graph is chordal, so optimal coloring is possible in polynomial time, which is why some modern compilers use SSA-based allocation or linear scan for JITs. So the core trade-off is allocation quality versus compile time.
Poor performance in a hot loop is often caused not by the algorithm but by register pressure causing spills and reloads, and recognizing this lets you respond at the source level — for example by inlining or shrinking variable live ranges.
Code & Formula
# 레지스터 할당(그래프 컬러링) — 간섭 그래프를 k개 물리 레지스터로 그리디 색칠하고, 실패하면 스필한다.
interference = {
"t1": {"t2", "t3"},
"t2": {"t1", "t3", "t4"},
"t3": {"t1", "t2", "t4"},
"t4": {"t2", "t3", "t5"},
"t5": {"t4"},
}
spill_cost = {"t1": 3, "t2": 1, "t3": 5, "t4": 2, "t5": 4} # 접근횟수*중첩깊이 근사치
K = 3 # 사용 가능한 물리 레지스터 수
def simplify_order(graph, k):
g = {n: set(neigh) for n, neigh in graph.items()}
stack, spilled = [], []
while g:
low_degree = [n for n, neigh in g.items() if len(neigh) < k]
if low_degree:
n = min(low_degree, key=lambda n: spill_cost[n]) # 차수<k 정점을 스택으로
else:
n = min(g, key=lambda n: spill_cost[n] / max(1, len(g[n]))) # 잠재적 스필 후보
spilled.append(n)
stack.append(n)
for neigh in g.values():
neigh.discard(n)
del g[n]
return stack, spilled
def color(order, graph, k):
colors = {}
for n in reversed(order):
used = {colors[m] for m in graph[n] if m in colors}
available = [c for c in range(k) if c not in used]
colors[n] = available[0] if available else None # None = 실제 스필
return colors
order, potential_spills = simplify_order(interference, K)
colors = color(order, interference, K)
print(f"제거 순서(스택): {order}")
print(f"단계에서 걸러진 잠재 스필 후보: {potential_spills}")
for t, c in colors.items():
where = f"R{c}" if c is not None else "MEMORY(spill)"
print(f" {t} -> {where}")
docs/code/algorithms/algorithms-22.py
Exercise
Pick a small function, compile it at -O0 and -O2, compare the assembly, and count how the number of stack-slot accesses (spills/reloads) changes.
Practical Connection
The EVM is a stack machine rather than a register machine, so its 16-deep stack limit effectively creates the same kind of pressure — Solidity's "stack too deep" error is isomorphic to a spill that pushes local variables out to memory.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.