寄存器分配算法：图着色 vs 线性扫描

寄存器分配是编译器后端最关键的优化之一。物理寄存器数量有限，如何将无限多的虚拟寄存器映射到有限的物理寄存器上，直接影响生成代码的性能。本文深入对比图着色和线性扫描两大经典算法。

一、问题建模：冲突图

两个虚拟寄存器在程序的某一点同时存活时，它们之间存在冲突（interference），不能分配到同一个物理寄存器。所有冲突关系构成一张无向图——冲突图。

type InterferenceGraph struct {
    nodes map[int]*Node
    edges map[int]map[int]bool
}

type Node struct {
    id     int
    degree int
    color  int // 分配的物理寄存器编号
    spill  bool
}

func (g *InterferenceGraph) AddEdge(a, b int) {
    if g.edges[a] == nil {
        g.edges[a] = make(map[int]bool)
    }
    if g.edges[b] == nil {
        g.edges[b] = make(map[int]bool)
    }
    if !g.edges[a][b] {
        g.edges[a][b] = true
        g.edges[b][a] = true
        g.nodes[a].degree++
        g.nodes[b].degree++
    }
}

二、图着色算法

图着色将寄存器分配转化为 K-着色问题（K 为物理寄存器数量）。Chaitin-Briggs 算法是经典实现，核心步骤：

Simplify（简化）

反复移除度数小于 K 的节点并压栈。这些节点一定可以被着色。

func (g *InterferenceGraph) Simplify(k int) []int {
    stack := make([]int, 0)
    worklist := g.getAllNodes()
    for len(worklist) > 0 {
        found := false
        for i, nodeID := range worklist {
            if g.nodes[nodeID].degree < k {
                stack = append(stack, nodeID)
                g.removeNode(nodeID)
                worklist = append(worklist[:i], worklist[i+1:]...)
                found = true
                break
            }
        }
        if !found {
            // 所有节点度数 >= K，需要 spill
            break
        }
    }
    return stack
}

Select（选择）

从栈中弹出节点，为其分配一个与邻居不同的颜色。如果找不到可用颜色，标记为 spill。

func (g *InterferenceGraph) Select(stack []int, k int) {
    for len(stack) > 0 {
        nodeID := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        g.restoreNode(nodeID)
        usedColors := make(map[int]bool)
        for neighbor := range g.edges[nodeID] {
            if g.nodes[neighbor].color >= 0 {
                usedColors[g.nodes[neighbor].color] = true
            }
        }
        color := -1
        for c := 0; c < k; c++ {
            if !usedColors[c] {
                color = c
                break
            }
        }
        if color >= 0 {
            g.nodes[nodeID].color = color
        } else {
            g.nodes[nodeID].spill = true
        }
    }
}

三、线性扫描算法

线性扫描由 Poletto 和 Sarkar 于 1999 年提出，按程序顺序一次性扫描所有活跃区间，复杂度 O(n log n)，远低于图着色的 O(n²)。

type LiveInterval struct {
    vreg   int
    start  int // 起始指令位置
    end    int // 结束指令位置
    preg   int // 分配的物理寄存器
}

func LinearScan(intervals []LiveInterval, k int) {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].start < intervals[j].start
    })
    active := make([]LiveInterval, 0)
    freeRegs := make([]int, k)
    for i := range freeRegs {
        freeRegs[i] = i
    }
    for _, interval := range intervals {
        // 过期活跃区间
        active = expireOldIntervals(active, interval.start, freeRegs)
        if len(freeRegs) == 0 {
            // 需要 spill：选择结束最晚的活跃区间
            spillIdx := selectSpillCandidate(active)
            if active[spillIdx].end > interval.end {
                interval.preg = active[spillIdx].preg
                active[spillIdx] = interval
            }
        } else {
            interval.preg = freeRegs[len(freeRegs)-1]
            freeRegs = freeRegs[:len(freeRegs)-1]
            active = append(active, interval)
        }
    }
}

四、算法对比

LLVM 3.0 后引入了 Greedy Register Allocator，结合了线性扫描的速度和图着色的质量，成为现代编译器的主流选择。