Skip to content
TheChatArchiveThe Chat Archive
ClaudeClaude Haiku 4.5· anthropicHugging Face Frontier Reasoning Traces

Explain graph coloring register allocation. Construct an interference graph and explain…

  1. User

    Explain graph coloring register allocation. Construct an interference graph and explain what happens when it's not k-colorable: spilling to memory.

  2. Claude Assistant

    This is a great question about compiler optimization, specifically about register allocation using graph coloring. Let me provide a comprehensive explanation.

    Graph Coloring Register Allocation

    Overview

    Graph coloring register allocation is a technique used by compilers to allocate variables to a limited number of CPU registers. The idea is to minimize memory access by keeping variables in registers when possible.

    Key Concepts

    1. Interference Graph: A graph where:

      • Each node represents a variable/value
      • An edge between two nodes means those variables interfere (are live at the same time)
      • Two variables that are live simultaneously cannot use the same register
    2. k-coloring: Assigning one of k colors (representing k available registers) to each node such that no two adjacent nodes have the same color

    3. Spillable: If we can't k-color the graph with k registers, we need to spill variables to memory (stack)

    Construction of Interference Graph

    The process:

    1. Perform liveness analysis to determine which variables are live at each program point
    2. For each instruction, if two variables are both live after that instruction, add an edge between them
    3. The resulting graph captures all conflicts

    What happens when not k-colorable?

    When the graph has a chromatic number greater than k (the number of available registers):

    1. Spilling: Select a variable and store it in memory instead of a register
    2. Add Load/Store Instructions: Before using a spilled variable, load it from memory; after modifying it, store back to memory
    3. Rebuild Graph: After spilling, rebuild the interference graph with the remaining variables
    4. Retry Coloring: Attempt to color the modified graph again

    Spilling Strategy

    Common heuristics for selecting which variable to spill:

    • Lowest degree heuristic: Spill the variable with the fewest conflicts

    • Cost-based: Consider the frequency of use (variables used in loops cost more to spill)

    • Weight/Degree ratio: Prioritize spilling variables with high cost relative to their interference degree

    A concrete example helps illustrate how this works in practice.

    Graph Coloring Register Allocation

    Overview

    Graph coloring register allocation maps variables to a limited number of CPU registers by modeling the problem as a graph coloring problem:

    • Nodes = variables/values
    • Edges = interference (two variables are live at the same time)
    • Colors = available registers
    • Goal = color the graph with k colors (k available registers)

    Building an Interference Graph

    Step 1: Liveness Analysis

    First, determine which variables are live at each instruction:

    // Example code
    {
        int a = 5;          // a is live here
        int b = 10;         // a, b are live
        int c = a + b;      // a, b, c are live
        int d = a * 2;      // a, c, d are live (b is dead)
        int e = c + d;      // c, d, e are live (a is dead)
        return e;           // e is live
    }
    

    After liveness analysis:

    a: live from line 1 to line 4
    b: live from line 2 to line 3
    c: live from line 3 to line 5
    d: live from line 4 to line 5
    e: live from line 5 to line 6
    

    Step 2: Build Interference Graph

    Add an edge between variables that are simultaneously live:

    Variables live together:
      Instruction 2: {a, b}       → edge (a, b)
      Instruction 3: {a, b, c}    → edges (a, b), (a, c), (b, c)
      Instruction 4: {a, c, d}    → edges (a, c), (a, d), (c, d)
      Instruction 5: {c, d, e}    → edges (c, d), (c, e), (d, e)
    

    Resulting Graph:

           b
          /|
         / |
        a--c--e
        |\ | /
        | \|/
        d--+
        
    Edges: (a,b), (a,c), (a,d), (b,c), (c,d), (c,e), (d,e)
    

    k-Coloring: Assigning Registers

    With k=3 registers (R0, R1, R2):

    Greedy coloring algorithm:
    1. Color 'a' → R0
    2. Color 'b' → R1 (can't use R0, adjacent to a)
    3. Color 'c' → R2 (can't use R0 or R1, adjacent to both)
    4. Color 'd' → R1 (can't use R0 or R2, but R1 is free)
    5. Color 'e' → R0 (can't use R1 or R2, but R0 is free)
    
    Result:
      a → R0
      b → R1
      c → R2
      d → R1 ✓
      e → R0 ✓
    

    This graph IS 3-colorable! ✓


    When NOT k-Colorable: Spilling

    Same code, but only k=2 registers:

    Try to color with R0, R1:
    1. Color 'a' → R0
    2. Color 'b' → R1
    3. Color 'c' → ? (adjacent to both a and b)
       CONFLICT! Need 3 colors but only have 2.
    

    The graph is NOT 2-colorable ✗

    Spilling Strategy

    When we can't color, we spill (move to memory):

    1. Choose a variable to spill (usually lowest-degree node)
       Strategy: Spill 'c' (has degree 4)
       
    2. Create memory location for 'c': [sp - 4]
    
    3. Insert load/store instructions:
       Original:
         int c = a + b;        // c in register
         int d = a * 2;
         int e = c + d;        // use c
       
       After spilling c:
         MOV R0, [sp - 4]      // load c from memory
         ADD R1, R0, R1        // d = a + c
         MOV R0, [sp - 4]      // load c again
         ADD R0, R1            // e = c + d
    
    4. Rebuild interference graph without 'c':
       (a, b), (a, d), (b, d), (d, e), (a, e)
       
    5. Try coloring again:
       a → R0
       b → R1
       d → R0 (not adjacent to a... wait, it IS)
       
       Still can't! May need to spill more variables.
    

    Complete Spilling Algorithm

    ALGORITHM: GraphColoringRegisterAllocation(variables, k_registers)
    
    REPEAT:
        1. Build interference graph G from variables
        
        2. IF graph is k-colorable THEN
            Return register assignment
           
        3. ELSE
            // Select variable to spill
            v = SelectSpillCandidate(G)
            
            // Insert loads/stores
            InsertLoadStore(v)
            
            // Remove from consideration
            variables.remove(v)
            
            // Try again with remaining variables
    UNTIL success
    

    Spill Cost Heuristics

    Different strategies for selecting which variable to spill:

    1. LOWEST DEGREE:
       Spill variable with fewest neighbors
       
    2. LOWEST COST/DEGREE:
       spill_priority = use_frequency / node_degree
       
    3. PRIORITY-BASED:
       // Prefer to spill:
       - Variables not in loops (low frequency)
       - Variables with many conflicts (high degree)
       - Large-sized variables
       - Variables used less frequently
    

    Visual: Before and After Spilling

    Before Spilling (k=2, FAILS)

    Graph:    a---b
              |\ /|
              | c |
              |/ \|
              d---e
    
    Chromatic number = 3
    Available colors = 2
    ❌ IMPOSSIBLE
    

    After Spilling c (k=2, SUCCESS)

    Graph:    a---b
              | X |
              |   |
              d---e
              |   |
              +---+
    
    Simplified graph (c moved to memory):
    a → R0
    b → R1
    d → R0
    e → R1
    
    ✓ 2-colorable!
    
    Code modified:
      LOAD Rc, [sp-4]     // load spilled c
      ADD d, a, Rc        // d = a + c
      LOAD Rc, [sp-4]     // load c again
      ADD e, Rc, d        // e = c + d
      STORE [sp-4], Re    // store e back
    

    Key Takeaways

    ConceptExplanation
    InterferenceVariables that can't share a register (live simultaneously)
    k-colorableCan assign k or fewer colors to all nodes without conflicts
    SpillingMoving variables to memory (stack) when not enough registers
    Graphs that remain non-k-colorableMay require multiple rounds of spilling
    Register pressureHigh interference → more spilling → slower code

    This technique balances speed (registers are fast) vs. availability (limited number of registers).

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.