register-allocator-graph-color
The complete graph-coloring register allocator is implemented in ~/register_allocator.py. Here's the architecture:
Core Algorithm (Chaitin-Briggs)
1. BUILD: Parse three-address IR → CFG → Live variable analysis → Interference graph
2. SIMPLIFY: Remove nodes with degree < K (K=15 allocatable x86-64 registers)
3. COALESCE: Merge move-related nodes if merged node has < K significant-degree neighbors (Briggs criterion)
4. FREEZE: If stuck, freeze a move-related node (convert to non-move)
5. SPILL: Mark lowest-cost/degree node for spilling (cost = Σ 10^loop_depth)
6. SELECT: Assign colors in reverse simplify order using greedy graph coloring
Key Components:
parse_tac() - Parses three-address code supporting label L:, dest = src1 op src2, mov, bcond, br, load, store, neg/not_ unary opsbuild_cfg() - Identifies basic blocks, computes pred/succ edges, detects natural loops via back-edgesliveness_analysis() - Iterative dataflow: in[i] = use[i] ∪ (out[i] - def[i]), out[i] = ∪ in[succ]build_interference() - Rule: for instruction i defining d, all variables in live_out[i] interfere with d (except move sources)chaitin_briggs_alloc() - Full iterative simplify/coalesce/freeze/spill loop with greedy select phaseverify_allocation() - Rebuilds interference graph and validates no conflicting assignmentsRegister Set: 15 x86-64 GP registers (rax, rbx, rcx, rdx, rsi, rdi, rbp, r8-r15), reserving rsp for stack. Spilled registers get [rsp - offset] stack slots.
All 18 tests pass with comprehensive edge case coverage: | Test | What it verifies | |------|-----------------| | `test_empty_program` | Handles empty input | | `test_single_register` | Single vreg assignment | | `test_simple_expression` | t1=r0+r1, t2=t1*r2 - correct coloring | | `test_live_range_interference` | t1,t2,t3 chain with proper interference edges | | `test_move_coalescing` | t2=t1 gets same color as t1 | | `test_cfg_branching` | If-else with join - t2 defined in 2 branches | | `test_loop_spill_cost` | Loop body correctly identified | | `test_coalescing_chain` | t1=t2=t3 chain through mov | | `test_interference_with_moves` | Move-related nodes don't interfere | | `test_diamond_cfg` | Diamond-shaped control flow | | `test_multiple_basic_blocks` | 4 blocks with chained branches | | `test_nested_loop` | Outer+inner loop depth computation | | `test_copy_chain_elimination` | 3-mov chain → all same register | | `test_high_pressure` | 18 vregs for K=15 → spills 3 | | `test_spill_and_reload` | 20 vregs → spills 6 | | `test_extreme_pressure` | 30 vregs → spills 16 | | `test_api_usage` | Programmatic alloc_from_instrs() + verify_allocation() | | `test_large_loop` | Loop with 5 active vregs | Each test runs `verify_allocation()` which rebuilds the interference graph and asserts **no two interfering virtual registers share the same physical register**. All verification passes.
{"model": "claude-sonnet-4-20250514", "problem_class": "register-allocator-graph-color", "result": "passed", "tests": 18}The complete graph-coloring register allocator is implemented in ~/register_allocator.py. Here's the architecture:
Core Algorithm (Chaitin-Briggs)
1. BUILD: Parse three-address IR → CFG → Live variable analysis → Interference graph
2. SIMPLIFY: Remove nodes with degree < K (K=15 allocatable x86-64 registers)
3. COALESCE: Merge move-related nodes if merged node has < K significant-degree neighbors (Briggs criterion)
4. FREEZE: If stuck, freeze a move-related node (convert to non-move)
5. SPILL: Mark lowest-cost/degree node for spilling (cost = Σ 10^loop_depth)
6. SELECT: Assign colors in reverse simplify order using greedy graph coloring
Key Components:
parse_tac() - Parses three-address code supporting label L:, dest = src1 op src2, mov, bcond, br, load, store, neg/not_ unary opsbuild_cfg() - Identifies basic blocks, computes pred/succ edges, detects natural loops via back-edgesliveness_analysis() - Iterative dataflow: in[i] = use[i] ∪ (out[i] - def[i]), out[i] = ∪ in[succ]build_interference() - Rule: for instruction i defining d, all variables in live_out[i] interfere with d (except move sources)chaitin_briggs_alloc() - Full iterative simplify/coalesce/freeze/spill loop with greedy select phaseverify_allocation() - Rebuilds interference graph and validates no conflicting assignmentsRegister Set: 15 x86-64 GP registers (rax, rbx, rcx, rdx, rsi, rdi, rbp, r8-r15), reserving rsp for stack. Spilled registers get [rsp - offset] stack slots.
All 18 tests pass with comprehensive edge case coverage: | Test | What it verifies | |------|-----------------| | `test_empty_program` | Handles empty input | | `test_single_register` | Single vreg assignment | | `test_simple_expression` | t1=r0+r1, t2=t1*r2 - correct coloring | | `test_live_range_interference` | t1,t2,t3 chain with proper interference edges | | `test_move_coalescing` | t2=t1 gets same color as t1 | | `test_cfg_branching` | If-else with join - t2 defined in 2 branches | | `test_loop_spill_cost` | Loop body correctly identified | | `test_coalescing_chain` | t1=t2=t3 chain through mov | | `test_interference_with_moves` | Move-related nodes don't interfere | | `test_diamond_cfg` | Diamond-shaped control flow | | `test_multiple_basic_blocks` | 4 blocks with chained branches | | `test_nested_loop` | Outer+inner loop depth computation | | `test_copy_chain_elimination` | 3-mov chain → all same register | | `test_high_pressure` | 18 vregs for K=15 → spills 3 | | `test_spill_and_reload` | 20 vregs → spills 6 | | `test_extreme_pressure` | 30 vregs → spills 16 | | `test_api_usage` | Programmatic alloc_from_instrs() + verify_allocation() | | `test_large_loop` | Loop with 5 active vregs | Each test runs `verify_allocation()` which rebuilds the interference graph and asserts **no two interfering virtual registers share the same physical register**. All verification passes.
{"model": "claude-sonnet-4-20250514", "problem_class": "register-allocator-graph-color", "result": "passed", "tests": 18}