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.
Where it lands in Jayverse
- Verex/DeFi contracts: treat "stack too deep" as a spill-cost problem. When a Solidity function hits the limit, shrink live ranges or split the function first, rather than reflexively raising the optimizer's aggressiveness, since the quality-versus-compile-time trade-off is the same one the card describes.
- CI: lint for functions approaching the stack limit before they fail. Add a check across Verex, DeFi and Bridge contracts that flags functions with many simultaneously-live locals, since that is the same interference-graph pressure that eventually forces a spill.
- Auditor: review optimizer-flag changes as a quality-vs-speed decision, not a default toggle. When a contract needs -O2-equivalent settings to compile, record why, the same way the card frames allocation quality against compile time.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| spilled to memory | (레지스터 부족으로) 값을 메모리로 밀어내다 · 컴파일러가 레지스터 할당에 실패했을 때 · "is spilled to memory" |
| register pressure | 레지스터 압박(동시에 살아있는 값이 많아 부족한 상태) · 핫루프 성능 저하의 원인을 지목할 때 · "register pressure causing spills and reloads" |
| hot loop | 자주 반복 실행되는 루프(성능에 민감한 구간) · 성능 문제의 원인 위치를 가리킬 때 · "Poor performance in a hot loop" |
| isomorphic to | ~와 구조적으로 동일한 · 전혀 다른 두 현상이 같은 원리임을 지적할 때 · "is isomorphic to a spill that pushes local variables" |
| stack too deep | (솔리디티) 스택 깊이 초과 오류 · EVM 스택 제한 때문에 발생하는 컴파일 에러 · "stack too deep error is isomorphic to a spill" |
| Chaitin-style heuristics | 채이틴 방식의 휴리스틱(그래프 색칠 근사 알고리즘) · NP-완전 문제를 실용적으로 푸는 방법 · "compilers use Chaitin-style heuristics" |
| at the source level | 소스 코드 수준에서 · 문제에 대응하는 위치를 가리킬 때 · "respond at the source level" |
| SSA | 정적 단일 할당(Static Single Assignment) · 각 변수가 한 번만 대입되는 중간표현 형태, 다항시간 채색이 가능해지는 조건 · "In SSA form the interference graph is chordal" |
| JITs | 즉시 컴파일러(Just-In-Time compilers) · 실행 시점에 즉석 컴파일하는 방식, 선형 스캔 레지스터 할당과 함께 언급 · "linear scan for JITs" |
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/.