LC

Implement Register Allocation Using Graph Coloring

hard5/8

Function Prologue and Epilogue Implement Instruction Selection Using Tree Pattern Matching

Language

Compiler

2.0s Limit 256MB

Implementation

Implement register allocation using graph coloring.

Requirements:

Compute liveness analysis for all variables
Build interference graph from live ranges
Implement graph coloring algorithm
Handle register spills to stack
Allocate physical registers to virtual registers
Test with programs that require spills
Handle x86-64 register constraints

Why This Matters

Chaitin's graph-coloring allocation, which you are implementing, ran in IBM's compilers for decades and remains the textbook standard; LLVM's greedy allocator and the linear-scan allocators in V8 and HotSpot are its descendants, engineered for compile speed. Register allocation quality is often the single biggest codegen factor in hot-loop performance.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0